[C++] (백준 11051 번) 이항 계수 2

 

문제출처: 백준
문제 링크: https://www.acmicpc.net/problem/11051
난이도: ★★☆☆☆

• 문제 분류: 다이나믹 프로그래밍 (dp)

[문제]

 

---

[분석]

항상 풀던 dp문제이다.base case의 경우, 이항계수의 기본 성질을 base case로 하면 된다.또한, n>k가 되면 이항계수를 구할 수 없다.

다음의 경우가 BASE CASE가 된다.

Recursive case의 경우 다음 표를 보면 담번에 이해된다.

다음 같은 규칙이 성립되는 이유는 다음과 같다.

규칙을 이항계수 식으로 표현하면 다음과 같다.

이 공식을 조합 규칙에 따라 변환한 뒤, 풀어보았다.

 

다음 공식으로 테이블의 법칙은 증명가능하다.

 

이제 점화식을 구하면 다음과 같다.

• 점화식

 

---

[코드]

#include<iostream>
using namespace std;

unsigned long long dp[1001][1001];


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

	for(int i=1;i<=n;i++) {
		dp[i][i]=1;
		dp[i][0]=1;
	}


	if(n>=2){
		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])%10007;
	
		}
	}	


	
	cout<<dp[n][k]<<endl;
	
}

n>k의 경우 코드로 구현 시, 0으로 구현하면 결과에 아무런 영향을 미치지 않는다.

문제에서 이미 이 경우는 주지 않는다고 표기