[C++] 백준 11051번 이항 계수 2

 

다이나믹 프로그래밍 문제입니다.

 

이항 계수 (N K)를 10007로 나눈 나머지를 출력하는 문제입니다.

이항 계수는 아래와 같은 규칙을 가집니다.

 

          1

        1  1

      1  2  1

    1  3   3  1 

  1  4   6   4  1 

1  5  10  10  5  1

 

값들은 위에 두개의 값의 합으로 이루업지니다.

이를 코드로하면 다음과 같습니다.

map[i][j] = (map[i - 1][j] + map[i - 1][j - 1])

 

#include <iostream>
using namespace std;

int map[1010][1010];

int main(int argc, char *argv[])
{
   int N, K;
   cin >> N >> K;

   for (int i = 0; i < 1010; ++i) {
      for (int j = 0; j < 1010; ++j) {
         map[i][j] = 0;
      }
   }
   map[1][1] = 1;
   
   for (int i = 2; i <= N + 1; ++i) {
      for (int j = 1; j <= N + 1; ++j) {
         map[i][j] = (map[i - 1][j] + map[i - 1][j - 1]) % 10007;
      }
   }

   cout << map[N + 1][K + 1] << endl;
   return 0;
}