[백준] 11051번 - 이항 계수 2 (C++ / 파이썬) 문제 및 풀이

문제) 백준 - 동적 계획법 (Dynamic programming) - 이항 계수 2

-> www.acmicpc.net/problem/11051

11051번: 이항 계수 2

 

주어지는 N과 K가 최대 1000이므로 기본 조합 공식으로 팩토리얼로 구한다면 시간 초과가 날 것이다. 따라서 우리는 동적 계획법을 이용하여 시간을 줄일 것이다. 

고등학교 수학 시간에 조합 관련 개념에서 우리는 다음과 같은 수식을 배웠다. (기억이 안난다면, 지금 알아 놓도록 하자.) 이 식을 이용해 우리는 동적 계획법의 수열을 쉽게 새울 수 있다. 

우리가 구할 값을 dp[n][k]라 했을 때, dp[1][1] = dp[1][0] = 1로 초기화 후 모든 i, j에 대해 dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]를 구해주면 된다. 이때, IndexError와 나머지에 대한 처리를 조심하도록 하자.

 

 

 

C++ 소스 코드)

#include <iostream>
using namespace std;
int dp[1001][1001] = { 0, };

int main() {
	int n, k;
	cin >> n >> k;

	dp[1][1] = 1;
	dp[1][0] = 1;

	for (int i = 2; i <= n; i++) {
		for (int j = 0; j <= k; j++) {
			if (j == 0 || i == j) dp[i][j] = 1;
			else {
				dp[i][j] = dp[i - 1][j - 1] % 10007 + dp[i - 1][j] % 10007;
			}
		}
	}
	cout << (dp[n][k] % 10007);
	return 0;
}

 

Python 소스 코드)

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
dp = [[0] * (n + 1) for _ in range(n + 1)]

dp[1][1] = dp[1][0] = 1

for i in range(2, n + 1):
    for j in range(k + 1):
        if (j == 0) or (i == j): dp[i][j] = 1
        else:
            dp[i][j] = dp[i - 1][j - 1] % 10007 + dp[i - 1][j] % 10007

print(dp[n][k] % 10007)