[백준 34301] Exact Change (C#, C++) - soo:bak

문제 링크

34301번 - Exact Change

설명

가격 N이 주어질 때, 1, 5, 15, 30, 150달러 지폐를 사용해서 정확히 N달러를 만들되, 총 지폐 수가 최소가 되도록 각 지폐 개수를 구하는 문제입니다.

접근법

지폐 종류는 적지만, 항상 그리디가 맞는지는 직접 보장되지 않으므로 최소 지폐 개수를 구하는 DP로 처리하는 편이 안전합니다.

dp[i]를 i달러를 만드는 데 필요한 최소 지폐 수라고 두고, 각 금액에서 다섯 종류의 지폐를 한 장씩 써 보는 방식으로 갱신합니다. 동시에 어떤 지폐를 마지막에 썼는지도 저장해 두면, N부터 거꾸로 따라가면서 각 지폐가 몇 장 쓰였는지 복원할 수 있습니다.

N ≤ 1000이므로 이 방법으로도 충분합니다.

---

Code

C#

using System;

class Program {
  static void Main() {
    int n = int.Parse(Console.ReadLine()!);
    int[] bills = { 1, 5, 15, 30, 150 };
    int[] dp = new int[n + 1];
    int[] prev = new int[n + 1];

    const int INF = 1_000_000_000;
    for (int i = 1; i <= n; i++) {
      dp[i] = INF;
      prev[i] = -1;
    }

    for (int i = 1; i <= n; i++) {
      for (int j = 0; j < bills.Length; j++) {
        int bill = bills[j];
        if (i >= bill && dp[i - bill] + 1 < dp[i]) {
          dp[i] = dp[i - bill] + 1;
          prev[i] = j;
        }
      }
    }

    int[] count = new int[5];
    int current = n;
    while (current > 0) {
      int idx = prev[current];
      count[idx]++;
      current -= bills[idx];
    }

    Console.WriteLine($"{count[0]} {count[1]} {count[2]} {count[3]} {count[4]}");
  }
}

C++

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

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

  int n;
  cin >> n;

  vector<int> bills = {1, 5, 15, 30, 150};
  const int INF = 1e9;
  vector<int> dp(n + 1, INF), prev(n + 1, -1);
  dp[0] = 0;

  for (int i = 1; i <= n; i++) {
    for (int j = 0; j < (int)bills.size(); j++) {
      int bill = bills[j];
      if (i >= bill && dp[i - bill] + 1 < dp[i]) {
        dp[i] = dp[i - bill] + 1;
        prev[i] = j;
      }
    }
  }

  vector<int> count(5, 0);
  int current = n;
  while (current > 0) {
    int idx = prev[current];
    count[idx]++;
    current -= bills[idx];
  }

  cout << count[0] << " " << count[1] << " " << count[2] << " "
       << count[3] << " " << count[4] << "\n";

  return 0;
}