[93] C++(Cpp) 백준 11051번: 이항계수 2 문제 (Dynamic programming, 동적 계획법, 조합)

문제

자연수 N\(N\)과 정수 K\(K\)가 주어졌을 때 이항 계수 (NK)\(\binom{N}{K}\)를 10,007로 나눈 나머지를 구하는 프로그램을 작성하시오.

입력

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

출력

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

예제 입력 1 복사

5 2

예제 출력 1 복사

10

 

 

 

 

<풀이>

 이 문제는 N과 K가 주어지면 NCK % 10007의 값을 출력하는 문제이다.

우리가 아는 단순한 조합공식 nCr = nPr / r! 을 사용하면 계산하는 도중에 오버플로우가 나버린다.

 

이를 방지하기 위해 조합의 성질 중 하나를 이용할 수 있다.

 

위의 공식은 파스칼의 삼각형을 보면 더 이해가 잘 될 것이다.

출처: https://www.google.com/url?sa=i&amp;url=https%3A%2F%2Fm.blog.naver.com%2FPostView.naver%3FisHttpsRedirect%3Dtrue%26blogId%3Dvollollov%26logNo%3D220915481071&amp;psig=AOvVaw1cq7Gs-8LqpWPD3g__ZfjW&amp;ust=1664266232607000&amp;source=images&amp;cd=vfe&amp;ved=0CAkQjRxqFwoTCLCq1IGBsvoCFQAAAAAdAAAAABAD

 

이제 이 공식을 이용해 계산한 값들을 저장시켜 계속 이용하는 dynamic programming으로 원하는 값을 구하면 된다.

 

 

 

<제출한 코드>

#include <iostream>
using namespace std;

long long combination(int n, int r){
    long long dp[n+1][n+1];

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

    for (int i = 2; i <= n; i++){
        for (int j = 2; j <= n; j++){
            if (i > j) dp[i][j] = (dp[i-1][j-1] + dp[i-1][j]) % 10007;  //nCr = n-1Cr-1 + n-1Cr
        }
    }
    return dp[n][r];
}

int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, K;
    cin >> N >> K;
    cout << combination(N, K);

    return 0;
}