BOJ [11501] 이항 계수 2

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

1. 분류

다이나믹 프로그래밍

2. 풀이

파스칼의 삼각형이 이항계수를 나타낸다는 것을 알고 있었다면 쉽게 풀리는 문제이다.

최상단 1을 초기화하고 이후부터 좌측, 우측 끝단을 1로 만든 후 가운데 숫자를 만들어내면 끝이다.

2차원 배열 d[y][x]가 이항계수에 들어갈 숫자들을 저장한다.

가장 윗 줄부터 하나씩 채워넣으며 N, K를 구하면 된다.

3. 소스코드

#include <cstdio>

long long d[1001][1001] = { 0 };

int main()
{	
	int n, k;

	scanf("%d %d", &n, &k);

	for (int i = 0; i <= n; i++)
	{
		d[i][i] = d[i][0] = 1;

		for (int j = 1; j <= i - 1; j++)
			d[i][j] = (((d[i - 1][j - 1] % 10007) + (d[i - 1][j]) % 10007)) % 10007;
	}

	printf("%llu\n", d[n][k]);

	return 0;
}