백준(baekjoon) [C] - 1010번: 다리 놓기

https://www.acmicpc.net/problem/1010

1010번: 다리 놓기

---

#include <stdio.h>  // 다리 놓기


int main()  // 조합 mCn 처음 factorial로 구현 --> 값이 너무 커져서 구현 x
{
	int t;
	scanf("%d", &t);

	unsigned long long int combination[30][30];
	combination[1][0] = combination[1][1] = 1;
	for (int i = 2; i <= 29; i++)
	{
		combination[i][0] = 1;
		for (int j = 1; j < i; j++)
			combination[i][j] = combination[i - 1][j - 1] + combination[i - 1][j];
		combination[i][i] = 1;
	}

	for (int i = 0; i < t; i++)
	{
		int n, m;
		scanf("%d %d", &n, &m);

		printf("%llu\n", combination[m][n]);
	}

	return 0;
}

---

MEMO

-- 문제를 읽고 나서 바로 확통수업에서 공부했던 조합(nCr)이 떠올라서 구현

-- nC0 과 nCn 은 항상 1

-- nCr = n-1Cr-1 + n-1Cr 을 통해서 2차원 배열에 값 저장 및 활용(DP)

 

!! 조합 구현 기억하기 !!