[알고리즘/문제풀이/BOJ 11051번] 이항 계수 2

이항 계수 2문제는 이항 계수 점화식뿐만 아니라 다이나믹 프로그래밍 기법을 활용하는 문제입니다. (n, k) = (n-1, k-1) + (n-1, k)라는 사실과 배열을 활용하여 (n, k)를 미리 계산한 후 출력함으로써 풀 수 있습니다. 다이나믹 프로그래밍을 할 때 기교를 발휘하면 배열의 크기는 1차원 배열 [1001]까지 줄일 수 있습니다. 작성한 코드에서는 2차원 배열 [2][1001]로 작성하였습니다.

---

#include<stdio.h>
//NCK
int N, K;
int result[2][1001];
int i=1;

int main(void) {
	scanf("%d %d", &N, &K);

	result[0][0] = 1;
	result[1][0] = 1;
	while (1) {
		for (int j = 1; j < 1001; j++) {
			result[i % 2][j] = (result[(i - 1) % 2][j] + result[(i - 1) % 2][j - 1]) % 10007;
		}
		if (i == N) break;
		i++;
	}

	printf("%d\n", result[i%2][K]);
}

 

문제의 지문은 다음의 링크에서 확인할 수 있습니다.

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