알고리즘 풀이/백준(Boj)

백준(BOJ) 11051번 이항 계수 2

100win10 2019. 7. 30. 01:27

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

문제

자연수 N과 정수 K가 주어졌을 때 이항 계수 (NK)를 10,007로 나눈 나머지를 구하는 프로그램을 작성하시오.


나의 풀이:


이항계수(N, K) 를 구하는 방법은 (N-1, K-1) + (N-1, K) 이고 재귀적으로 호출해주면 된다. 하지만 N이 1000이기에 시간내에 풀기에는 불가능하다. 


ex ) 이항계수(5, 2)를 예로 이항계수(4,1) 부터 쭉 재귀적으로 내려가서 답을 구한 다고 가정하면 또 (4,2)를 구할 때에도 (3,1), (2,1) 등 구한 값을 다시 구해야 한다. 


따라서 중복이 되는 경우는 메모이제이션을 통하여 중복을 제거 해주어야 한다.



코드 ( C++ )

#include <iostream>

#include <cstring>

using namespace std;


int N, K;

const int MAX = 1000 + 1;

int cache[MAX][MAX];

const int MOD = 10007;

int bino(int n, int k)

{

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


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

if (ret != -1)

return ret;

return ret = ((bino(n - 1, k) + bino(n - 1, k - 1)))%MOD;   // 10007로 나눈 나머지를 구해주자.

}


int main()

{

memset(cache, -1, sizeof(cache)); // 초기화

cin >> N >> K;

int ans = bino(N, K);

cout << ans << endl;

return 0;

}