[11051 C++, python] 이항 계수 2

문제 구분 - Dynamic Programing

11051번: 이항 계수 2

동기들과 랜덤실버디펜스할때 처음 봤던 문제다.

사실 처음 봤다고 말하기도 좀 애매한게 여러 번 풀었던 유형이었다.

(그런데도 못맞..)

이 문제는 파이썬으로 팩토리얼 돌려버리면 풀리긴 하는데 문제 출제 의도는 dp였다고 생각한다. 

//
//  main.cpp
//  11051
//
//  Created by jisu on 2022/02/06.
//

#include <iostream>

using namespace std;

int bino[1001][1001] = {0,};

int main(void) {
    int n, k;
    cin >> n >> k;
    //nCr = n-1Cr-1 + n-1Cr
    bino[1][0] = 1;
    bino[1][1] = 1;
    for (int i=2; i<=n; i++){
        for (int j=0; j<=k; j++){
            if (j==0 || j==i){
                bino[i][j] = 1;
            }
            else{
                bino[i][j]=bino[i-1][j-1]%10007+bino[i-1][j]%10007;
            }
        }
    }
    cout << bino[n][k]%10007 << "\n";
    return 0;
}

조합 관련해서 고등학교때 가장 중요했던 성질 하나가 바로 

nCr = n-1Cr-1 + n-1Cr

이었는데 이 성질을 dp에다가 적용할 수 있었다. 

파스칼의 삼각형도 잊어먹어서 리마인드겸 사진도 올려본다.

from math import factorial
n, k = map(int, input().split())
result = factorial(n)//(factorial(k) * factorial(n - k))
print(result % 10007)

파이썬으로 풀면 풀리긴 하더라..