백준 14916 - 거스름돈 (자바 - 그리디)

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

14916번: 거스름돈

 

* 문제 요약

편의점 카운터에서 일하는데 손님이 2원짜리와 5원짜리 동전으로만 거스름돈을 달라고 한다.

여기서 2원짜리 동전과 5원짜리 동전은 무한정으로 많이 가지고 있다고 가정한다.

거스름돈을 줄 때 동전의 갯수가 최소가 되도록 거슬러 주어야 한다.

거스름돈이 n 인 경우, 최소 동전의 갯수가 몇 개인지 알려주는 프로그램을 작성하시오.

 

예를 들어 거스름돈이 15원이면 5원짜리 3개를, 거스름돈이 14원이면 5원짜리 2개와 2원짜리 2개로 총 4개를,

거스름돈이 13원이면 5원짜리 1개와 2원짜리 4개로 총 5개를 주어야 동전의 갯수가 최소가 된다.

 

* 입력

거스름돈 액수 n (1 <= n <= 100,000) 이 주어진다.

 

* 출력

거스름돈 동전의 최소 갯수를 출력한다. 만약 거슬러줄 수 없다면 -1 을 출력한다.

 

* 예시

 

* 해결 과정

문제 요약의 마지막 글에서 나온 예시를 보면 거스름돈이 13원일 경우 5원짜리 1개와 2원짜리 4개로 총 5개의 동전을 주어야 한다고 나와있다.

이 예시를 보면 동전을 최소화 시키겠다고 무턱대고 5원짜리 동전을 최대한 많이 주는 방식으로 풀면 반드시 틀렸습니다 라는 결과를 얻게 된다.

 

예를 들어 거스름돈이 13원일때 동전 갯수를 최소화 시키겠다고 5원짜리를 최대화 시켜 2개를 준다면 3원이 남게되는데, 이렇게 되면 2원짜리 동전으로 남은 거스름돈을 줄 수 없는 상황이 발생하게 된다.

반면에 5원짜리 동전을 하나만 준다면 8원이 남게되므로 2원짜리 동전 4개를 주면 된다.

 

즉, 이 문제는 5원짜리 동전을 하나도 쓰지 않는 경우부터, 5원짜리 동전을 최대로 쓰는 경우까지 모두 탐색하며 5원, 2원짜리 동전을 통해 거슬러줄 수 있는 모든 경우의 수 중에서 동전을 최소로 사용하는 경우를 찾는 방식으로 문제를 풀어야 한다.

 

* 코드

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

public class Main {
    public static void main(String[] args) throws NumberFormatException, IOException {
        new Main().solution();
    }

    private void solution() throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int money = Integer.parseInt(br.readLine());

        int result = Integer.MAX_VALUE;
        int count = 0;
        boolean check = false;
        while (5 * count <= money) {
            int number = money - (count * 5);
            if (number > 0) {
                int twoCount = number / 2;
                int change = number % 2;
                if (change != 0) {
                    count++;
                    continue;
                } else if (change == 0) {
                    check = true;
                    result = Math.min(result, count + twoCount);
                }
            } else if (number == 0) {
                result = Math.min(result, count);
                check = true;
            }
            count++;
        }

        if (check) {
            bw.write(result + "\n");
        } else {
            bw.write(-1 + "\n");
        }
        bw.flush();
        bw.close();
        br.close();
    }
}

 

결국 기본적으로 동전을 작게 사용하는 경우를 찾아야 하기 때문에 5원짜리 동전을 먼저 사용하는 걸 우선시하는 방식으로 하여 각 단계마다 최적의 경우를 찾아가는 그리디 알고리즘 방식으로 문제를 풀었다.

 

그리고 거스름돈을 걸러줄 수 있는 경우 사용된 동전의 갯수를 따로 저장해준 뒤 다음 단계로 넘어가는, 이른바 메모이제이션 기법을 활용하였는데,

각 경우마다 사용된 동전의 갯수를 구해내고 (작은문제 해결) 이를 각각의 결과마다 비교해나가며 최종적으로 동전이 가장 적게 사용되는 경우를 찾아냈다.(큰문제 해결)

즉, 각각의 작은문제 마다 산출된 결과값들을 저장해나가는 메모이제이션 기법을 이용해 큰 문제를 해결하였으므로 다이나믹 프로그래밍 기법 또한 활용되었다고 볼 수 있다.