[백준 11051] 이항 계수 2

www.acmicpc.net/problem/11051

11051번: 이항 계수 2

이항계수를 구하는 문제이다. 

nCk = n!/k!(n-k)!이지만 n과 k가 1000까지 입력을 받기 때문에 저 식대로 계산하면 오버플로우가 발생한다.

 

그래서 파스칼의 삼각형을 사용하여 구해준다.

파스칼의 삼각형은 dp를 사용해서 구한다.

 

nCk = dp[i][j] 

if j=0 or i=j then 1

else dp[i][j] = dp[i-1][j-1] + dp[i-1][j]로 식을 세울 수 있다.

 

#include <stdio.h>

using namespace std;

int dp[1001][1001];
int main(void)
{
  int n, k;
  scanf("%d%d", &n, &k);

  if (n / 2 < k)
  {
    k = n - k;
  }

  dp[1][0] = 1, dp[1][1] = 1;
  for (int i = 1; i <= n; i++)
  {
    for (int j = 0; j <= n; j++)
    {
      if (j == 0 || j == i)
      {
        dp[i][j] = 1;
      }
      else
      {
        dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j]) % 10007;
      }
    }
  }

  printf("%d\n", dp[n][k]);
  return 0;
}