[BOJ/백준 11051][C++] 이항계수 2

문제

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

 

문제 내용

정수 n과 k를 입력 받아서 nCk를 구하는 문제이다.

이항계수에 대한 특징을 알면 문제를 쉽게 풀 수 있다.

nCk = (n-1)Ck + (n-1)C(k-1) 라는 것을 이용하면 된다.

 

문제 풀이

dynamic programming (dp)를 사용하여 문제를 풀면 된다.

이항계수의 특성상 k==0 이거나 n==k 일 때는 값이 1이 된다.
그 이외의 경우는 nCk = (n-1)Ck + (n-1)C(k-1) 를 만족한다.

위 점을 고려하여, 이중 반복문을 사용하여 dp값을 하나하나 채워가면 된다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

//이항계수
////nCk = (n-1)Ck + (n-1)C(k-1)

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	//입력
	int n, k;
	cin >> n >> k;
	vector<vector<int>>dp(n + 1, vector<int>(k + 1, 0));
	
	//문제 해결
	for (int i = 1; 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] + dp[i - 1][j - 1])%10007;
		}
	}

	//결과 출력
	cout << dp[n][k] << '\n';
}

 

문제 코드 설명

1) 입력

vector<vector<int>>dp(n + 1, vector<int>(k + 1, 0)); 는 크기가 (n+1)*(k+1)인 이차원 배열 dp를 만들고 0으로 초기화 한다는 의미이다.

 

2) 문제 해결

문제에서 nCk의 값을 10007로 나눈 나머지를 출력하라고 했으므로, %10007을 식에 적용한다.