[C/C++] 이항 계수 2

11051: 이항 계수 2 문제

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

11051번: 이항 계수 2

 

이항 계수 문제는 사실상 Dynamic Programming 문제 중에서 가장 기초적이면서 유명한 문제라고 할 수 있다.

사실 Dynamic Programming 풀지 않아도 이항계수 계산을 범위를 초과되지 않은 기준 내에서 해결가능하기는 하다.

하지만 DP를 이용해서 푸는 것이 값이 매우 커질 경우 더 효과적일 수도 있다. 

 

 DP로 풀기 위해서는 공식하나를 알아야하는데 바로  nCr=n-1Cr + n-1Cr-1 이다.

즉 nCr을 구하기 위해서는 n-1Cr 과 n-1Cr-1을 구해야하므로 Combination() 함수를 재귀적으로 호출하여 풀면 된다.

다만, 그냥 재귀적으로 호출을 할 경우 그 경우의 수가 지수적으로 커지고, 반복되는 문제를 비효율적으로 계속 접근하면서 풀기 때문에 dp[][]배열을 이용하여 한번 지나간 경우에 그 값을 저장하고 다음에 참조할 경우 저장되어 있는 값을 반환하면 된다.

 

 즉, if(dp[n][k]==0)   dp[n][k]=(Combination(n-1,k)+ Combination(n-1,k-1)) 으로 저장하고 만약 저장되어 있다면  return dp[n][k]하면 된다.

 

 또한 기저조건들을 결정해주고 문제에서 나와있듯이 10007로 나눈다면 문제를 쉽게 풀 수 있다!

 

#include <stdio.h>

int dp[1001][1001]; //0으로 끝남, 1로 끝남,이친수의 개수

int Combination(int n, int k)
{
  if(n<k)
    return 0;
    
  if(k==0 || n==k)
  {
    dp[n][k]=1;    
  }    
  if(k==1 || n==k+1)
  {
    dp[n][k]=n;    
  }    

  if(dp[n][k]==0)  
  {
    dp[n][k]=(Combination(n-1,k)+ Combination(n-1,k-1))%10007;
  }
  return dp[n][k];
}

int main(void)
  {
    int n,k;
    scanf("%d %d",&n,&k); //nCr=n-1Cr + n-1Cr-1
    int result= Combination(n,k);
  
    printf("%d",result%10007);
  }