[백준 9084] 동전 (C#, C++) - soo:bak

문제 링크

9084번 - 동전

설명

여러 종류의 동전이 주어질 때, 금액 M을 만드는 경우의 수를 구하는 문제입니다.

각 동전은 무한히 사용할 수 있고, 순서가 다른 것은 같은 경우로 칩니다.

접근법

동전을 하나씩 추가하면서 각 금액을 만드는 방법 수를 늘려갑니다.

예를 들어 1원, 2원, 5원 동전으로 7원을 만든다면, 먼저 1원만으로 각 금액을 만드는 방법을 세고, 다음에 2원을 추가해서 방법을 더하고, 마지막으로 5원을 추가합니다.

2원 동전을 추가할 때, 7원을 만드는 방법은 기존 방법에 5원을 만들던 방법을 더한 것과 같습니다. 2원을 하나 쓰고 나머지 5원을 만들면 되기 때문입니다.

이렇게 동전 종류별로 순서대로 처리하면, 같은 조합을 중복으로 세지 않습니다.

---

Code

C#

using System;

class Program {
  static void Main() {
    var t = int.Parse(Console.ReadLine()!);
    while (t-- > 0) {
      var n = int.Parse(Console.ReadLine()!);
      var coins = Array.ConvertAll(Console.ReadLine()!.Split(), int.Parse);
      var m = int.Parse(Console.ReadLine()!);

      var dp = new int[m + 1];
      dp[0] = 1;
      foreach (var c in coins) {
        for (var x = c; x <= m; x++)
          dp[x] += dp[x - c];
      }

      Console.WriteLine(dp[m]);
    }
  }
}

C++

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

typedef vector<int> vi;

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

  int t; cin >> t;
  while (t--) {
    int n; cin >> n;
    vi coin(n);
    for (int i = 0; i < n; i++) cin >> coin[i];
    int m; cin >> m;

    vi dp(m + 1, 0);
    dp[0] = 1;
    for (int c : coin) {
      for (int x = c; x <= m; x++)
        dp[x] += dp[x - c];
    }

    cout << dp[m] << "\n";
  }

  return 0;
}