[백준 2225] 합분해 (C#, C++) - soo:bak

문제 링크

2225번 - 합분해

설명

0부터 N까지의 정수 K개를 더해서 합이 N이 되는 경우의 수를 구하는 문제입니다. 같은 수를 여러 번 사용할 수 있고, 순서가 다르면 다른 경우로 칩니다.

접근법

동적 프로그래밍으로 해결합니다. k개의 수로 합 n을 만드는 경우의 수를 저장합니다.

k개의 수로 n을 만드는 방법을 마지막 수가 0인 경우와 1 이상인 경우로 나눕니다.

마지막 수가 0인 경우, 앞의 k-1개의 수로 n을 만들어야 합니다. 이 경우의 수는 k-1개로 n을 만드는 방법의 수와 같습니다.

마지막 수가 1 이상인 경우, 마지막 수에서 1을 빼면 k개의 수로 n-1을 만드는 것과 같아집니다. 마지막 수가 1 이상인 모든 경우는 1을 빼는 변환을 통해 k개로 n-1을 만드는 경우와 일대일 대응됩니다.

따라서 k개로 n을 만드는 방법의 수는 k-1개로 n을 만드는 방법의 수와 k개로 n-1을 만드는 방법의 수를 더한 것입니다.

초기값으로 1개의 수로 n을 만드는 방법은 n 자체를 선택하는 한 가지뿐입니다. 모든 연산은 10억으로 나눈 나머지를 구합니다.

---

Code

C#

using System;

class Program {
  const int MOD = 1_000_000_000;

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

    var dp = new int[k + 1, n + 1];
    for (var i = 0; i <= n; i++) dp[1, i] = 1;

    for (var i = 2; i <= k; i++) {
      for (var j = 0; j <= n; j++) {
        var fromLeft = j > 0 ? dp[i, j - 1] : 0;
        dp[i, j] = (fromLeft + dp[i - 1, j]) % MOD;
      }
    }

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

C++

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

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

const int MOD = 1'000'000'000;

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

  int n, k; cin >> n >> k;
  vvi dp(k + 1, vi(n + 1, 0));
  for (int i = 0; i <= n; i++) dp[1][i] = 1;

  for (int i = 2; i <= k; i++) {
    for (int j = 0; j <= n; j++) {
      int left = (j > 0) ? dp[i][j - 1] : 0;
      dp[i][j] = (left + dp[i - 1][j]) % MOD;
    }
  }

  cout << dp[k][n] << "\n";

  return 0;
}