[백준 11051] 이항 계수 2 (C#, C++) - soo:bak

문제 링크

11051번 - 이항 계수 2

설명

이항 계수를 10007로 나눈 나머지를 구하는 문제입니다.

접근법

파스칼의 삼각형 성질을 이용합니다. n개에서 k개를 고르는 경우의 수는, n-1개에서 k-1개를 고르는 경우와 n-1개에서 k개를 고르는 경우의 합과 같습니다.

이차원 배열을 만들어 위에서부터 채워나갑니다. 각 행의 양 끝은 1이고, 나머지 칸은 바로 윗줄의 두 값을 더해서 구합니다. 매번 나머지 연산을 적용하여 값이 커지지 않도록 합니다.

---

Code

C#

using System;

class Program {
  const int MOD = 10007;

  static void Main() {
    var parts = Console.ReadLine()!.Split();
    var n = int.Parse(parts[0]);
    var k = int.Parse(parts[1]);

    var dp = new int[n + 1, n + 1];
    for (var i = 0; i <= n; i++) {
      dp[i, 0] = 1;
      dp[i, i] = 1;
      for (var j = 1; j < i; j++) {
        dp[i, j] = (dp[i - 1, j - 1] + dp[i - 1, j]) % MOD;
      }
    }

    Console.WriteLine(dp[n, k]);
  }
}

C++

#include <bits/stdc++.h>
using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;

const int MOD = 10007;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, k; cin >> n >> k;
  vvi dp(n + 1, vi(n + 1, 0));
  for (int i = 0; i <= n; i++) {
    dp[i][0] = dp[i][i] = 1;
    for (int j = 1; j < i; j++) {
      dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j]) % MOD;
    }
  }
  cout << dp[n][k] << "\n";

  return 0;
}