개요

[링크]백준 11051번 : 이항계수

• 입력
  첫째 줄에 (N)과 (K)가 주어진다. (1 ≤ (N) ≤ 1,000, 0 ≤ (K) ≤ (N))

• 출력

  $( \binom{N}{K}) 를 10,007로 나눈 나머지를 출력한다.

  접근 방식

  파스칼의 삼각형을 이용한 nCr= n-1Cr-1 + n-1Cr 식을 사용한다.

코드

#include<iostream>

using namespace std;
const int N = 1001;
const int K = 1001;
const int MOD = 10'007;
int dp[N][K],inputN=0,inputK=0;

void input() {
	cin >> inputN>>inputK;
}
void solution() {

	dp[1][1] = 1;
	dp[1][0] = 1;

	//n은 2부터 inputN까지
	for (int i = 2; i <= inputN; i++) {
		//k는 0부터 n까지
		for (int j = 0; j <= i; j++) {
			//k==0이거나 n==k이면 1 넣어줌
			if (j == 0 || j==i) {
				dp[i][j] = 1;
				continue;
			}
			//아니라면 nCr= n-1Cr + n-1Cr-1 공식에 따라 넣어줌,
			dp[i][j] = (dp[i-1][j]%MOD + dp[i-1][j-1]%MOD) % MOD;
		}
	}
	cout << dp[inputN][inputK];
}

int main() {
	input();
	solution();
}

문풀후생

처음에 j==0이거나 j==i이면 dp[i][j]=1을 넣어준 후,
밑에는 dp[i+1][j+1] = dp[i][j-1] + dp[i][j];
이렇게 짜서 중간에 빈 값이 생겨버려서 꼬였다.

위에 dp[i][j]=1 이면 똑같이 dp[i][j]=dp[i-1][j]+dp[i-1][j-1];
이런 식으로 짜야한다.