DP - 빠르게 이항 계수 구하기

관련 문제:

백준 11051번 - 이항 계수 2 https://www.acmicpc.net/problem/11051

11051번: 이항 계수 2

이항 계수 C(N, K)를 10007로 나눈 나머지를 구한다.

 

 

풀이:

DP(N, K) = 이항 계수 C(N, K)

이 경우 DP(N, K) = DP(N-1, K-1) + DP(N-1, K)

 

해설:

1) "DP(N, K) = DP(N-1, K-1) + DP(N-1, K)"의 의미

기본적인 이항 계수의 성질 중 하나인 C(n, r) = C(n-1, r-1) + C(n-1, r)을 DP로 바꿔 쓴 것이다.

사실 이 성질을 몰라도 C(0, 0)부터 C(N, K)까지 쭉 파스칼의 삼각형(삼각형 형태로 나열한 이항 계수)을 써보면 쉽게 규칙을 알 것이니 답을 구할 수 있을 것이다.

 

2) Top-down으로 풀어보기

베이스 케이스인 C(n, 0) = C(k, k) = 1까지 적용하여 메모이제이션을 써서 쉽게 코드를 작성할 수 있을 것이다.

 

3) Bottom-up으로 풀어보기

Bottom-up 방식으로 코드를 작성하려면 조금 더 생각을 해봐야 한다.

일단 파스칼의 삼각형을 조금 회전해서 써봐야겠다. 그럼 뭐를 어떻게 계산해야 하는지 보일 것이다.

1 1 1 1 1

1 2 3 4

1 3 6        ...

1 4

1

저걸 2차원 배열에 그대로 넣었다고 생각해보자. arr[n][k] = arr[n - 1][k] + arr[n][k - 1]인 것이 보인다.

음, 그래서 C(N, K)가 배열의 어느지점인데? 얘를 다시 C(N, K)로 봐야겠다.

 

(0, 0)  (1, 1)  (2, 2)  (3, 3)  (4, 4)

(1, 0)  (2, 1)  (3, 2)  (4, 3)

(2, 0)  (3, 1)  (4, 2)                    ...

(3, 0)  (4, 1)

(4, 0)

규칙이 보인다! C(N, K)의 값은 arr[n - k][k]에 저장되고 있다. 이제 코드로 쉽게 바꿀 수 있겠다.

 

Pseudocode:

i) 메모이제이션(Top-down)을 사용했을 때

//사실 이건 뭐 원본 코드랑 거의 똑같다... 제출할 때는 뒤에 %10007로 나눠주는 것 잊지 말것!

int dp(int n, int k) {
    if (memo[n][k] != 0) return memo[n][k];
    else if (k == 0 || k == n) return memo[n][k] = 1;                      //이게 베이스겠지. C(n, 0)과 C(k, k)는 1이니까!
    else return memo[n][k] = dp(n - 1, k - 1) + dp(n - 1, k);         //C(n, r) = C(n-1, r-1) + C(n-1, r)
}

 

ii) Bottom-up

N, K = 주어진 N, K;

DP[K+1];                  //1로 초기화 되어야 함. DP계산 시 바로 직전 행 값과 이번 행 값만 쓰므로 1차원 배열이면 충분함.

for (i = 1 ~ n - k) {
    for (j = 1 ~ k) {
        DP[j] += DP[j - 1];
    }
}

C(N, K) = DP[K];