백준 11051 : 이항 계수 2

이항 계수 2 성공

 

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

256 MB

36844

13801

10836

38.291%

문제

자연수 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

출처

• 데이터를 추가한 사람: BaaaaaaaaaaarkingDog, kimsu00215, loveyourself, skyoliver
• 문제를 만든 사람: baekjoon

알고리즘 분류

• 수학
• 다이나믹 프로그래밍
• 조합론

메모

 

코드 

 

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int dp[1001][1001];
int main() {

    int n,k;
    cin >> n >> k;
    
    dp[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < i + 1; j++) {
            if (j == 0 || j == i+1) {
                dp[i][j] = 1;
                //cout << dp[i-1][j] << ' ';
            }
            else {
                dp[i][j] = (dp[i-1][j - 1] + dp[i-1][j]) % 10007;
                //cout << dp[i][j] << ' ';
            }
            
        }
        //cout << endl;
    }
    cout << dp[n][k]<<endl;


    return 0;
}