[11051번] 이항 계수 2

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. Dynamic Programming

2. 파스칼 삼각형

아래 그림의 원리를 이용한다면 빠르게 DP를 구할 수 있다.

0C0부터 시작해서 nCk까지 Dynamic Programming을 통해 구할 수 있게 된다.

combi[1001][1001]배열의 의미는 combi[n][k] 즉, nCk의 의미를 가지도록 배열을 구성한 것이다.

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

소스 코드 : 

#include <iostream>
#include <memory.h>
 
using namespace std;
 
int combi[1001][1001];
int main()
{
    int n, k;
 
 
    cin >> n >> k;
 
    combi[0][0] = 1;
    combi[1][0] = 1;
    combi[1][1] = 1;
 
    for (int i = 2; i <= n; i++)
    {
        for (int j = 0; j <= k; j++)
        {
            combi[i][j] = combi[i - 1][j - 1] % 10007 + combi[i - 1][j] % 10007;
            combi[i][j] %= 10007;
        }
    }
 
    cout << combi[n][k];
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>

combination dp 소스코드

#include <iostream>
 
#define MAX 101
#define MIN(a,b) (a < b ? a : b)
 
int comb[MAX][MAX];
 
void makeComb(int n, int r) {
    comb[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        int len = MIN(i, r);
        for (int j = 0; j <= len; j++) // 5C2는 있지만 2C5는 없다.
            comb[i][j] = comb[i - 1][j - 1] + comb[i - 1][j];
    }
}
 
int main() {
    int n = 10, r = 10;
    makeComb(n, r);
    for (int i = 0; i <= 10; i++) {
        for (int j = 0; j <= 10; j++) {
            printf("%4d", comb[i][j]);
        }
        printf("\n");
    }
}