[C++]백준 - 11051번 문제

11051번: 이항 계수 2 (acmicpc.net)

11051번: 이항 계수 2

 

11051번 : 이항 계수 2

---

자연수 N과 정수 K가 주어졌을 때 이항 계수

를 10,007로 나눈 나머지를 구하는 프로그램을 작성하시오.

 

입력

---

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

 

출력

---

를 10,007로 나눈 나머지를 출력한다.

 

 

 

---

 

생각해 볼 점

---

저번과 달리 입력 되는 N의 값이 1000까지 늘어났으며, 10007로 나눈 나머지를 출력해야 하는 조건도 붙었습니다.

 

단순히 생각하면, 11050번 때처럼 조합식으로 풀 수도 있지만, 10007로 나눈 나머지를 구하기도 전에 숫자가 int는 커녕 unsigned long long으로도 감당할 수 없는 큰 수가 될 것이 뻔합니다.

 

따라서, 방법은 파스칼의 삼각형을 따라 덧셈으로 구하는 방법 뿐입니다.

파스칼의 삼각형에 따라 구하려는 값 바로 위 단계의 인접한 두 숫자를 더한 값이 됩니다.

 

이 원리를 이용해서 재귀 함수를 이용한 풀이를 하는 것이 좋습니다.

 

다만, 단순히 수행 시간 단축을 위해 재귀만 하지 않고 동적 프로그래밍 기법을 이용하는 것이 좋겠습니다.

 

이렇게 하면, 모든 연산이 덧셈 형태로 이루어지기 때문에, 재귀 함수 return 시 10007로 나눈 나머지로 반환해도 정답은 동일합니다.

 

코드

---

#include <iostream>
using namespace std;
int dp[1001][1001] = {0,};


int solution(int N, int K)
{
    if(N <= 1) return 1;				
    if(dp[N][K] != 0) return dp[N][K];	//다이나믹 프로그래밍
    if(K == 0 || K == N)	//K의 값이 양 끝일 경우, 1을 반환
    {
        dp[N][K] = 1;
        return 1;
    }
    else
    {
        dp[N][K] = (solution(N-1, K-1) + solution(N-1, K)) % 10007;	//재귀
        return dp[N][K];
    }
    
}

int main()
{
    int N, K;
    
    cin >> N >> K;

    int result = solution(N,K);
    cout << result << "\n";
    return 0;
}

 

그 외

---

사전 지식이 조금 필요하니 이 문제를 풀기 전에 백준에서 단계적으로 풀어보기를 차근차근 해나가는 게 중요한 것 같습니다.