[BOJ/C++] 11051 이항계수 2

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

 

이항계수란 n개 중에 k개를 순서 없이 뽑는 조합의 수를 의미한다. 조합을 만들때 원소를 뽑거나, 안뽑거나 라는 두가지 선택지가 있기에

아래와 같은 식으로 나타낼 수 있다.

이렇게 팩토리얼로 나타낼 수도 있지만 이를 알고리즘으로 짜다가는 금방 overflow를 맞이할 것이다. 그렇기 때문에 아래 점화식을 사용하여 dp로 푸는 것이 더 효율적이다. 또한 이전 행의 값만 알면 다음 행을 구할 수 있기 때문에 일차원으로 구현하면 이항계수의 값만 큼 즉 (N*N+1)/2 개의 공간만으로도 표현 가능하다. 

아래가 이차원으로 구현했을 때 위가 일차원으로 구현했을때

 

#include<iostream>
using namespace std;

int main(){
    int n,k;
    cin >> n >> k;
    int dp[1001] = {0};
    dp[0] = 1;

    for (int i = 1; i <= n; i++) {
        for (int j = min(i, k); j > 0; j--) {
            dp[j] = (dp[j] + dp[j-1]) % 10007;
        }
    }

    cout << dp[k];

    return 0;
}

 

이때 j번째 요소를 계산할 때 갱신 전 j-1번째 요소를 사용해야하기 때문에 뒤에서부터 값을 채워넣어야한다!!!