[백준] 14916번 : 거스름돈 (JAVA)

🔗 문제 링크

https://www.acmicpc.net/problem/14916

---

📌 문제 개요

2원과 5원 동전을 사용하여 n원을 만들 때
동전의 최소 개수를 구하는 문제이다.

만약 정확히 만들 수 없다면 -1을 출력

---

📌 접근 방법

• 동전 개수를 최소로 하기 위해 5원을 먼저 최대한 사용
• 남은 금액이 2원으로 나누어 떨어지는지 확인
• 나누어 떨어지지 않으면 5원을 하나 줄이고 다시 확인
• 5원 개수가 0보다 작아지면 만들 수 없는 경우

---

📌 핵심 아이디어

• 5원을 최대한 사용하는 것이 동전 개수 최소에 유리하다.
• 단, 남은 금액이 홀수라면 2원으로 만들 수 없다.
• 따라서 5원 개수를 줄여가며 가능한 경우를 탐색

이 방식은 그리디(Greedy) 전략

---

📌 전체 코드

package no_14916;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class No14916 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n  = Integer.parseInt(br.readLine());
        int coin = n / 5;
        int result = 0;

        n = n % 5;

        while (coin >= 0){
            if(n % 2 == 0){
                result = coin + (n / 2);
                break;
            }
            coin--;
            n += 5;
        }

        if (coin < 0) {
            System.out.println(-1);
        } else {
            System.out.println(result);
        }
    }
}

---

📌 정리

• 5원을 먼저 최대한 사용하는 것이 핵심
• 남은 금액이 짝수인지 여부만 확인하면 된다
• 만들 수 없는 경우(1, 3 등)는 -1 처리

그리디 기본기를 다지는 좋은 문제