[BOJ] 백준 11051 이항 계수 2 / 동적 계획법(Dynamic-Programming)

이미지를 클릭하면 문제 사이트로 이동합니다.

---

 

 

💣 문제 이해

 

 

자연수 N과 정수 K가 주어졌을 때 이항 계수 (N K)를 10,007로 나눈 나머지를 구하는 문제이다.

 

동적 계획법(Dynamic Programming) 방식을 사용했다.

 

 

 

 

💭 풀이 과정

 

 

_nC_r = _n-1C_r + _n-1C_r-1  식 이 성립하게 된다.

사탕 4개 중에 2개를 선택할 때 (₄C₂) , 어떤 한 사탕을 제외한 3개 중에 2개를 뽑는 경우 (₃C₂) 와 그 한 사탕을 무조건 뽑고 남은 3개 중에 1개를 더 뽑는 경우 (₃C₁) 를 합한 것과 같기 때문이다.

 

 

이를 그림으로 나타낸 것이 파스칼의 삼각형이다.

 

 

점화식은  dp[i][j] = dp[i-1][j] + dp[i-1][j-1]  이다.

 

 

 

작성 언어: C++

 

#include <cstdio>

int dp[1001][1001] = {1, };
const int REMAIN = 10007;

int pascal(int mVal, int kVal){
    for (int i = 1; i <= mVal; ++i) {
        dp[i][0] = dp[i][i] = 1;
        for (int j = 1; j < i; ++j) {
        	// (a+b)%mod = (a%mod + b%mod)%mod 성질을 이용한 계산
            dp[i][j] = (dp[i-1][j] % REMAIN + dp[i-1][j-1] % REMAIN) % REMAIN;
        }
    }
    return dp[mVal][kVal];
}

int main(){
    int M, K;
    scanf("%d %d", &M, &K);
    printf("%d\n", pascal(M, K));
    return 0;
}

 

 

 

 

🏆 배운 점

 

 

DP로 푸는 피보나치 수열같은 느낌이 많이 들었다.

 

이 이전에 재귀함수로 짠 코드(메모이제이션 없이)도 있었는데 O(2^N) 답게 입력 값이 조금만 커지면 엄청난 시간이 걸렸다.

 

DP 배열을 채워서 풀다보니 O(N²) 이면 풀리게 되었다.

 

 

 

( + 몇 번 포스팅하면서 느껴지는 것이, 푼 것을 정리하면서 학습된 것을 또 한 번 생각하고 모르는 것은 더 찾아보면서 좀 더 가깝게 내 것이 된다는 느낌이 든다. )