[알고리즘] 동적 계획법 - 최적화된 이항 계수 구하기 (Dynamic Programming - Optimal Binomial Coefficient)

문제)

Description

교재와 강의자료를 참고하여, Algorithm 3.2를 최적화 하시오.

여기서 이항계수는 다음과 같이 변형하여 정의한다.

B[n][k] = 1, where k == 0 or k == n

B[n][k] = (B[n-1][k-1] + B[n-1][k]) % MAX

최적화된 알고리즘은 시간 복잡도가 O(nk), 공간 복잡도가 O(n)이어야 한다.

이 알고리즘의 구현은 구현 언어에 따른 실행 시간과 메모리 사용량이 크게 차이가 나므로,

이 문제에 한해서는 C, C++ 언어를 사용할 것을 권장한다.

파이썬 또는 자바 사용시에는 시간 초과, 메모리 초과를 피하기 어려울 것이다.

Input

첫 째줄에 이항계수의 n과 k, 그리고 MAX 값이 주어진다.

0 <= k <= n <= 200000

10 <= MAX <= 10000000

Output

첫 번째 줄에 변형 이항계수의 값 B[n][k]를 출력한다.

Sample Input 1

10 6 10000

Sample Output 1

210

Sample Input 2

15 7 10000

Sample Output 2

6435

Sample Input 3

15 7 100

Sample Output 3

35

 

---

Input) k,n <= 200,000

Output) nCk를 출력

 

알고리즘)

• 기존의 DP와 동일한 알고리즘을 적용한다.
• k는 min(k, n-k) 중에 한 개를 선택한다.
• 또한 1개의 배열을 사용하므로, 업데이트 되기 전의 배열을 저장해놓아야 한다.
• 이때 매 nCk는 MAX로 나눠준다.
• 최대 200,000이므로 배열의 크기는 100,000으로 고정한다.

코드)

int optimal_bin(int n, int k, int MAX){
    int B[100000] = {0,};       // 배열에 이항 계수를 저장함
    k = min(k, n-k);        // k를 좀 더 작은 애로 집어 넣음

    int temp, temp2;       // B[j-1]을 저장하는 원소

    for (int i = 0; i <= n; i++){
        for (int j = 0; j <= min(k, i); j++){
            if ((j == 0) || (j == n)){     //j == 0 혹은 j == n과 같다면 1을 저장함
                B[j] = 1;
                temp = 1;
            }
            else{
                // B[j] = B[j] + B[j-1];       // 이러면 B[j-1]은 이미 업데이트 된 상태이므로 기존의 B[j-1]을 저장한 무언가를 넣어줘야함
                temp2 = B[j];       // 변환되기 전의 B[j]를 넣음
                B[j] = (B[j] + temp) % MAX;
                temp = temp2;        // 변환되기 전의 B[j]를 넣음, temp는 다음 반복문, 즉 j+1으로 가서 기존의 B[j]의 역할을 수행함
            }
        }
        // for (int idx = 0; idx <= k; idx++){      // 과정을 출력함
        //         cout << B[idx] << " ";
        //     }
        //     cout << endl;
    }
    return B[k];
}

아주 쉽죠?

 

감사합니다.

 

 

 

지적 환영합니다.