백준 11051번 이항 계수 2

< 백준 11051번 이항 계수 2 - 마포 코딩박 >

사용한 알고리즘: DP


 순열조합의 nCk를 계산하는 문제였습니다. 단, n이 최대 10^3으로 꽤 크게 주어져서 DP를 활용하여 문제를 해결하였습니다.

문제풀이는 다음과 같습니다.

(1) (코드 7~8)
 dp[n][k] = nCk%10007 값으로 설정했습니다.

(2) (코드 16~25)
 nC0=1, nC1=n 임을 이용하여 dp[i][0]=1, dp[i][1]=i 의 초기 설정을 했습니다.
 nCk = n-1Ck + n-1Ck-1 임을 이용하여 dp[2][2] ~ dp[1000][1000] 까지 계산해주었습니다.

	#include <iostream>
	using namespace std;
	typedef long long ll;
	const int MOD = 10007;
	int N, K;
	// dp[n][k] = nCk % MOD 값
	ll dp[1001][1001];
	int main(){ios::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	for(int i=1; i<=1000; ++i){
	dp[i][1] = (ll)i;
	dp[i][0] = 1LL;
	}
	// dp 값 계산
	for(int i=2; i<=1000; ++i){
	for(int j=2; j<=1000; ++j){
	if(i==j){
	dp[i][j] = 1LL;
	break;
	}
	dp[i][j] = (dp[i-1][j] + dp[i-1][j-1])%MOD;
	}
	}
	cin >> N >> K;
	cout << dp[N][K]%MOD << '\n';
	return 0;
	}

view raw BOJ 11051.cpp hosted with ❤ by GitHub