[BOJ] 백준 11051번: 이항 계수 2

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

11051번: 이항 계수 2

 

중학교 수준의 수학 지식이 필요한 DP 문제입니다.

 

#include <bits/stdc++.h>
using namespace std;

const int MOD = 10007;
int N, K, dp[1001][1001];

void solve(){
	for(int i = 1; i <= N; ++i){
		dp[i][0] = 1;
		dp[i][i] = 1;
	}
	
	for(int i = 2; i <= N; ++i){
		for(int j = 1; j < i; ++j){
			dp[i][j] = (dp[i-1][j-1] + dp[i-1][j]) % MOD;	
		}
	}
	
	cout << dp[N][K];
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> N >> K;
	
	solve();
}

 

dp 문제는 1) table 정의 2) 점화식 찾기 3) 초기값 설정의 3단계로 일관성있게 풀이합니다.

 

1) table 정의

dp[i][j] : i choose j

 

2) 점화식 찾기

dp[i][j] = dp[i-1][j-1] + dp[i-1][j];

중학교 혹은 고등학교에서 조합을 배웠다면, 파스칼의 삼각형을 접해봤다면 쉽게 알 수 있는 점화식입니다.

 

3) 초기값 설정

dp[i][0] = 1; (i choose 0 = 1)

dp[i][i] = 1; (i choose i = 1)

 

시간복잡도는 O(N^2)입니다.