[C++/BOJ] 백준 11051 이항계수2 (DP) 알고리즘 문제풀이

문제 링크

백준티어 : 실버 1

 

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

11051번: 이항 계수 2

 

 

 

N과 K가 주어질때 그 이항계수의 값을 구하는 문제입니다.

이와 똑같은 문제인 이항계수1이 있는데 그것과 같은 풀이를 하면 시간초과가 납니다.

이 문제는 dp를 이용하여 풀어야합니다.

 

먼저 이항계수 nCk = (n-1)C(k-1)  + (n-1)Ck 입니다.

 

문제를 풀다보면 이항계수의 개념이 몇번 나오기때문에 외워두는 것이 편할것같습니다.

 

 

 

 

해답코드 :

 

#include<iostream>

#include<cstring>

using namespace std;

 

int n, k;

int dp[1001][1001];

 

int func(int n, int k) {

   if (k == 0 || n == k) return 1;

   int& ret = dp[n][k];

   if (ret != -1) return ret;

   return ret = (func(n - 1, k - 1) + func(n - 1, k)) % 10007;

}

 

int main() {

   cin >> n >> k;

   memset(dp, -1, sizeof(dp));

   cout << func(n, k);

}

 

 

 

이 풀이와 이항계수1의 차이를 찾아보면

 

#include<iostream>
#include<cstring>
using namespace std;
int n, k;
int dp[1001][1001];
int func(int n, int k) {
    if (k == 0 || n == k) return 1;
    int& ret = dp[n][k];
    if (ret != -1) return ret;
    return ret = (func(n - 1, k - 1) + func(n - 1, k)) % 10007;
}

int main() {
    cin >> n >> k;
    memset(dp, -1, sizeof(dp));
    cout << func(n, k);
}

 

초록색으로  색칠된 부분입니다.

 

코드 설명 :

 

=> 먼저 main에서 memset을 이용해 dp배열을 -1로 초기화합니다. 

(참고로 memset은  cstring을 memset을 해주어야합니다.)

 

dp[n][k]를 ret이라는 변수 설정과 함께 같은 주소를 가리키도록 해줍니다.

ret이 변경되면 연결되어있는 해당 dp[n][k]도 함께 변경됩니다.

 

만약 ret이 변경되었다면 답이 있는 것이므로 ret을 반환하고 없을경우 

이항계수를 구하는 식을 반환해줍니다

 

 

 

 

 

문제후기 : 실버1이지만 그렇게 어렵지 않습니다.

이 문제를 통해 &의 개념을 잡을 수 있었습니다.