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

문제 링크

2293번 - 동전 1

설명

n가지 종류의 동전이 주어지는 상황에서, n (1 ≤ n ≤ 100)과 각 동전의 가치, 그리고 목표 금액 k (1 ≤ k ≤ 10,000)가 주어질 때, 이 동전들을 사용하여 합이 k원이 되도록 만드는 경우의 수를 구하는 문제입니다.

각 동전은 무한히 사용할 수 있으며, 동전의 순서는 고려하지 않습니다. 즉, (1원 + 2원)과 (2원 + 1원)은 같은 경우로 취급합니다.

접근법

이 문제는 동적 프로그래밍으로 해결할 수 있습니다.

각 금액에 대해 그 금액을 만들 수 있는 경우의 수를 저장하면서, 동전을 하나씩 추가하며 갱신합니다.

핵심은 동전의 순서를 고려하지 않기 위해 순회 순서를 올바르게 설정하는 것입니다.

동전 종류를 먼저 순회하고, 각 동전에 대해 금액을 순회하면 각 동전을 한 번씩만 고려하게 되어 순서가 다른 중복을 자동으로 제거할 수 있습니다.

구체적으로, 금액 0부터 시작하여:

• 금액 0을 만드는 경우의 수는 1 (아무 동전도 사용하지 않음)
• 각 동전에 대해, 그 동전의 가치 이상인 모든 금액을 순회
• 금액 s를 만드는 경우의 수에, (s - 동전 가치)를 만드는 경우의 수를 더함

예를 들어, 동전이 [1, 2, 5]이고 목표 금액이 5원일 때:

• 초기: 경우의 수 = [1, 0, 0, 0, 0, 0] (인덱스 = 금액)
• 1원 동전 추가:
  • 1원: 0원 + 1원 = 1가지
  • 2원: 1원 + 1원 = 1가지
  • …
  • 5원: 4원 + 1원 = 1가지
  • 결과: [1, 1, 1, 1, 1, 1]
• 2원 동전 추가:
  • 2원: 기존 1 + (0원 + 2원) = 2가지
  • 3원: 기존 1 + (1원 + 2원) = 2가지
  • 4원: 기존 1 + (2원 + 2원) = 3가지
  • 5원: 기존 1 + (3원 + 2원) = 3가지
  • 결과: [1, 1, 2, 2, 3, 3]
• 5원 동전 추가:
  • 5원: 기존 3 + (0원 + 5원) = 4가지
  • 결과: [1, 1, 2, 2, 3, 4]

따라서 5원을 만드는 경우의 수는 4가지입니다:

1. 1+1+1+1+1
2. 1+1+1+2
3. 1+2+2
4. 5

이 방법은 각 동전을 한 번씩, 각 금액을 한 번씩 확인하므로 시간 복잡도는 O(n×k)입니다.

관련 문제: [백준 1789] 수들의 합 (C#, C++) - soo:bak

---

Code

C#

using System;

namespace Solution {
  class Program {
    static void Main(string[] args) {
      var input = Console.ReadLine()!.Split();
      var n = int.Parse(input[0]);
      var k = int.Parse(input[1]);

      var coins = new int[n];
      for (var i = 0; i < n; i++)
        coins[i] = int.Parse(Console.ReadLine()!);

      var dp = new int[k + 1];
      dp[0] = 1;

      foreach (var coin in coins) {
        for (var amount = coin; amount <= k; amount++)
          dp[amount] += dp[amount - coin];
      }

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

C++

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

typedef vector<int> vi;

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

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

  vi dp(k + 1, 0);
  dp[0] = 1;
  
  for (int coin : coins) {
    for (int amount = coin; amount <= k; amount++)
      dp[amount] += dp[amount - coin];
  }

  cout << dp[k] << "\n";
  
  return 0;
}