[백준 14916] 거스름돈 (C#, C++) - soo:bak

문제 링크

14916번 - 거스름돈

설명

거스름돈 n원을 2원, 5원 동전만으로 만들 때 동전 개수를 최소로 하는 값을 구하는 문제입니다. 만들 수 없으면 -1을 출력합니다.

접근법

동전 개수를 줄이려면 5원 동전을 가능한 많이 쓰는 것이 유리합니다.
먼저 5원 동전을 최대로 사용한 상태에서 시작하고, 남은 금액이 2원 동전으로 나누어떨어지지 않으면 5원 동전을 하나씩 줄이며 다시 확인합니다.
처음으로 나누어떨어지는 경우가 나오면 그 조합이 최소 동전 개수입니다. 끝까지 불가능하면 -1입니다.

---

Code

C#

using System;

class Program {
  static void Main() {
    int n = int.Parse(Console.ReadLine()!);
    int five = n / 5;

    while (five >= 0) {
      int remain = n - five * 5;
      if (remain % 2 == 0) {
        int answer = five + (remain / 2);
        Console.WriteLine(answer);
        return;
      }
      five--;
    }

    Console.WriteLine(-1);
  }
}

C++

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

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

  int n; cin >> n;
  int five = n / 5;

  while (five >= 0) {
    int remain = n - five * 5;
    if (remain % 2 == 0) {
      cout << (five + remain / 2) << "\n";
      return 0;
    }
    five--;
  }

  cout << -1 << "\n";
  return 0;
}