[백준 27106] Making Change (C#, C++) - soo:bak

문제 링크

27106번 - Making Change

설명

구매 금액 P센트(1≤P≤99)가 주어질 때, 1달러(100센트)에서 거슬러 줄 돈을 25, 10, 5, 1센트 동전으로 최소 개수로 표현하는 문제입니다.

접근법

거스름돈은 100에서 구매 금액을 뺀 값입니다. 동전 개수를 최소화하려면 큰 단위부터 최대한 사용해야 합니다.

25센트, 10센트, 5센트, 1센트 순으로 나누어 몫을 동전 개수로 취하고 나머지를 다음 동전으로 넘기면 됩니다. 미국 표준 동전 체계에서는 이 그리디 방식이 항상 최소 개수를 보장합니다.

---

Code

C#

using System;

class Program {
  static void Main() {
    var p = int.Parse(Console.ReadLine()!);
    var change = 100 - p;
    int[] coins = { 25, 10, 5, 1 };
    var result = new int[4];

    for (var i = 0; i < 4; i++) {
      result[i] = change / coins[i];
      change %= coins[i];
    }

    Console.WriteLine(string.Join(" ", result));
  }
}

C++

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

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

  int p; cin >> p;
  int change = 100 - p;
  int coins[4] = {25, 10, 5, 1};
  int cnt[4];

  for (int i = 0; i < 4; i++) {
    cnt[i] = change / coins[i];
    change %= coins[i];
  }

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

  return 0;
}