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

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

 

- 정답 코드

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

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine()); // 거스름돈 액수

        int result = -1; // 결과 저장 변수, 초기값 -1로 설정
        int five = n / 5; // 최대 5원 동전 갯수 // 13 / 5 = 2

        // 5원짜리 동전 개수 줄여가며 가능한 조합을 찾음
        while(five >= 0) {
            int remainder = n - (five * 5); // 13 - 2 * 5 = 3 // 13 - 1 * 5 = 8
            if(remainder % 2 == 0) { // 3 % 2 != 0  // 8 % 2 == 0
                result = five + (remainder / 2); // 1 + (8 / 2) = 1 + 4 = 5
                break; // 반복문 종료 
            }
            five--; // 5원짜리 동전 개수 하나 줄이고 다시 시도  // 1
        }
        System.out.println(result); // 5
    }
}

---

- 문제 풀이 

가장 큰 동전인 5원짜리를 최대한 많이 사용하고, 남은 금액을 2원짜리로 채워 최소 동전 개수를 찾는 방식을 사용합니다. 다음은 이 알고리즘의 흐름입니다:

1. 주어진 금액 n을 5원으로 나누어 최대한 많이 사용합니다.
2. 남은 금액이 2원으로 나누어 떨어지는지 확인합니다.
3. 나누어 떨어지지 않으면 5원짜리 동전 개수를 하나 줄이고 다시 시도합니다.
4. 5원짜리 동전 개수가 0이 될 때까지 반복합니다.
5. 거스름돈을 만들 수 없으면 -1을 반환합니다.