[백준 11051] 알고리즘 35일차 : 이항 계수 2

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

11051번: 이항 계수 2

수학3, 동적계획법 C++

이항계수를 동적계획법으로 푸는 문제 (간략)

 

작년 알고리즘 수업에서 배우고 또 비슷한 손코딩 문제가 시험에도 나왔었던 문제

이항계수였는지는 기억안남

DP에서 피보나치와 함께 배운 기억이 난다. 두 문제 모두 재귀를 배울때 나오는 개념들이지만

사실 시간복잡도면에서 보면 배열을 사용해서 반복문을 쓰는게 훨씬 효율적이다.

(이걸 동적계획법 부분에서 배움

매번 이런식이지 비효율적인거 실컷 가르쳐놓고 효율적인 방법 나중에 알려주기

교수님 : 하지만 이렇게 풀면 더 좋답니다~

말하는 감자들 : ..... )

 

암튼. 그래서 배열을 써서 값을 저장해가면서 푼다.

n행의 k열은 n-1행의 k-1열 + n-1행 k열 이니까.

이때도 사실 이차원 배열을 사용할 필요도 없이

일차원 배열 하나만 사용할 수 있다. 값을 갱신해갈때 순서를 왼쪽부터(인덱스 0부터) 시작하는게 아니라

오른쪽 부터 값을 갱신해가면 앞의 값을 손상시키지 않고 다음행의 값으로 갱신할 수 있다.

 

접근방법(요약)

1. 행,열 마다 반복문 돌면서 (n k) = (n-1 k-1) + (n-1 k) 사용하여 값 갱신 (덮어쓰기 식)

* 열은 k부터 0까지 순으로 돈다.

* 열 인덱스가 0이거나 i(행 인덱스)이면 값은 1

* 그냥 이항계수를 출력하는게 아니라 이항계수를 10007으로 나눈 값을 출력하는 것이기 때문에

애초에 값을 구해나갈때도 10007으로 나누어 떨어지는 만큼은 필요없다. (이 값을 그대로 저장하면 수가 범위를 초과한다.)

그래서 값을 배열에 담을 때 10007로 나눈 나머지를 배열에 저장한다.

 

반복문 종료 후 10007로 나눈 나머지를 출력하면 끝

 

소스코드

#include <iostream>
using namespace std;

int main(){
    int n, k;
    cin >> n >> k;
    
    int* BC = new int[k+1];
    for(int i = 1 ; i <= n ; i++){
        for(int j = k ; j >= 0 ; j--){
            if(j == 0 || j == i){
                BC[j] = 1;
            }
            else{
                BC[j] = BC[j-1]%10007 + BC[j]%10007;
            }
        }
    }
    cout << BC[k]%10007;
    
    return 0;
}