[C/C++ 백준 11051번] 이항 계수 (Silver 1)

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

11051번: 이항 계수 2

아이디어는 nCk = n/k * (n-1)C(k-1) 임을 이용하는 점화식이다. k가 1인 경우 nCk는 n, k가 0이면 1인 것도 인지하자.

처음 짠 코드는 다음과 같다. 배열을 처음에는 dp[1001][1001]로 했는데 실행이 안되서, nCk=nC(n-k)임을 이용했다.

 

#include <cstdio>
int main(void){
	int N, K;
	scanf("%d %d",&N ,&K);
	if(K>N/2)	K=N-K;
	int dp[1001][501]={};
	for(int i=1; i<=N; i++){
		for(int j=0; j<=i; j++){
			if(j==0)	dp[i][j]=1;
			else if(j==1)	dp[i][j]=i;
			else if(i==j)	dp[i][j]=1;
			else	dp[i][j]=(int)((double)i/j*dp[i-1][j-1]);
		}
	}
	printf("%d",(int)dp[N][K]);
}

 

그리고 런타임에러. 생각해보니, 모든 dp를 구할 필요가 없다. 그래서 일차원 dp(해당 경우의 dp만..? 따지는)를 설정해 다시 해보았는데,

 

#include <cstdio>
int main(void){
	int N, K;
	scanf("%d %d",&N ,&K);
	if(K>N/2)	K=N-K;
	long long int dp[1001]={0,N-K+1,};
	int cnt1=N-K+1;
	for(int i=2; i<=K; i++){
		cnt1++;
		dp[i]=(cnt1*dp[i-1])/i;
	}
	if(K==0)	printf("1");
	else	printf("%lld",dp[K]%10007);
}

 

곱셈이라 10007로 나누어야 한다는 조건을 만족시키기 까다롭다. 

사실 이항 계수를 구하는 식은 하나 더 있다. nCk = n-1Ck-1 + n-1Ck 인데, 이 식을 이용하면

 

#include <cstdio>
int main(void){
	int N, K;
	scanf("%d %d",&N ,&K);
	if(K>N/2)	K=N-K;
	int dp[1001][501];
	for(int i=1; i<=N; i++){
		for(int j=0; j<=K && j<=i; j++){
			if(j==0)	dp[i][j]=1;
			else if(j==i)	dp[i][j]=1;
			else	dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
			dp[i][j] = dp[i][j] % 10007;
		}
	}
	printf("%d",dp[N][K]);
}

 

이항 계수의 성질을 잘 알면 쉽게 풀 수 있지만, 모른다면 까다로워 보인다. 문제를 풀기 전에 성질을 알고 들어가자.