[BOJ] 백준 11051번 이항 계수 2 풀이

| |
백준 온라인 저지 백준 11051번 - 이항 계수 2 C++ 풀이


문제

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


입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ K ≤ N)


출력

(N,K)를 10,007로 나눈 나머지를 출력한다.


풀이

이 문제를 해결하기 위해서는 다음과 같은 이항 정리의 성질을 알고 있어야 한다.

(N,K) = (N-1,K-1) + (N-1,K)

이 성질이 이해되지 않는다면 이항 정리 관련 개념을 따로 찾아보기 바란다. 위와 같은 성질을 통해 재귀함수를 통해 이항 계수를 구할 수 있다는 것을 예측할 수 있다. 기저 사례는 다음과 같이 설정한다.

  • N과 K가 같다면 N개 중 K개를 뽑는 경우의 수이므로 반드시 1
  • K가 0이라면 아무것도 뽑지 않는 경우이므로 반드시 1

위 2개의 기저 사례로 재귀를 통해 구현할 수 있다.

그런데 역시 너무나 많은 중복 계산이 수반된다. 따라서 메모이제이션 기법을 이용한 다이나믹 프로그래밍을 통해 풀이한다.

그리고 숫자가 너무 커지는 것을 방지하기 위해 문제에서 10007로 답을 나눈 나머지를 구하라는 조건을 주었다. 모듈러 법칙에 따라 재귀 함수의 반환 부분에서 각각의 합의 요소에 모듈러를 적용해주고 최종 답에서 마지막으로 모듈러를 적용해주면 된다.


전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
#define MOD 10007
using namespace std;

int cache[1001][1001];

int bino(int n, int k){
   if(n==k || k==0) return 1;
   int& ret=cache[n][k]; // 메모이제이션
   if(ret!=0) return ret;
   return ret = bino(n-1,k-1)%MOD + bino(n-1,k)%MOD; // 모듈러 법칙
}

int main(){
   int n,k; cin>>n>>k;
   cout<<bino(n,k)%MOD;

   return 0;
}
0%