[백준 14916] 거스름돈 (Java) - 그리디, 다이나믹 프로그래밍

https://www.acmicpc.net/problem/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을 출력한다.

예제 입력 1 복사

13

예제 출력 1 복사

5

예제 입력 2 복사

14

예제 출력 2 복사

4

---

풀이

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();

        if (N==1 || N==3){
            System.out.println(-1);
            return;
        }

        if (N==2 || N==4){
            System.out.println(N/2);
            return;
        }

        int[] A = new int[N+1]; // 최소 거스름돈 개수
        int INF = 10000001;
        Arrays.fill(A,INF);

        // 5원으로 거슬러 줌
        for(int i=5; i<N+1; i+=5){
            A[i] = i/5;
        }

        // 2원으로 거슬러줌
        for(int i=2; i<N+1; i+=2){
            A[i] = Math.min(A[i], i/2);
        }

        for(int i=6; i<N+1; i++){
            A[i] = Math.min(A[i], A[i-5]+1);
            A[i] = Math.min(A[i], A[i-2]+1);
        }

        System.out.println(A[N] >= INF ? -1 : A[N]);
    }
}

• 그리디, 다이나믹 프로그래밍을 활용한 문제
• 백준의 '설탕배달'과 문제만 다르고 풀이방법은 100% 똑같다.
• 5원, 2원짜리 동전으로 거슬러주는 경우의 수 중 최솟값을 찾는 문제
• 문제는 5,2원짜리 동전으로 딱 나누어 떨어지지 않는 경우 -1을 출력해야 한다. 
• 5,2의 배수를 기준으로 나눌 수는 없다.
  • 예를들어, 거스름돈 13원을 거슬러줘야하는 경우 13은 5의배수도 아니고, 2의 배수도 아니지만
  • 5원 x 1개 + 2원 x 4개 = 13 의 조합으로 딱 나눠떨어지게 거슬러줄 수 있기 때문이다.

다이나믹 프로그래밍 일반 점화식

• 13원을 거슬러준다고 가정하고, 문제풀이를 한다고 생각했을 때 다이나믹프로그래밍 일반 점화식을 생각해보자
  • 이미 대부분 거슬러 줬고 나머지 금액을 거슬러줘야 된다고 생각했을때
  • 나머지 금액을 5원으로 거슬러 줄 수 있다면, 13원 - 5원 = 8원을 이미 거슬러줬을 것이다.
  • 나머지 금액을 3원으로 거슬러 줄 수 있다면, 13원 - 3원 = 10원을 이미 거슬러줬을 것이다.
  • 이 두가지 경우의 수 중 거슬러 준 동전 개수가 더 작은 경우의 수를 선택하면 된다.
  • A[N] = Math.min(A[N-5] + 1, A[N-3] + 1) 일 것이다.
• 배열 A를 N+1 크기로 선언한다.( 거스름돈 1원부터 시작하기 때문)
• A[i] = i원을 거슬러준 최소동전 개수이다.

이미 아는 수 입력하기

// 5원으로 거슬러 줌
        for(int i=5; i<N+1; i+=5){
            A[i] = i/5;
        }

        // 2원으로 거슬러줌
        for(int i=2; i<N+1; i+=2){
            A[i] = Math.min(A[i], i/2);
        }

• 5로 나누어떨어지는 수는 5로 나눈 몫으로 채운다.
• 2로 나누어떨어지는 수는 2로 나눈 몫과 비교해서 최솟값을 채워넣는다.

점화식 적용하기

        for(int i=6; i<N+1; i++){
            A[i] = Math.min(A[i], A[i-5]+1);
            A[i] = Math.min(A[i], A[i-2]+1);
        }

• i=6 ~ N까지 순회하면서

• A[i], A[i-3] + 1, A[i-5] + 1을 비교해서 최솟값을 입력한다.
• 점화식을 모두 적용 후, A[N]을 출력하면 된다.
• A[N] 값이 INF보다 크거나 같을 경우 5,2원짜리 동전으로 딱 맞게 거슬러줄 수 없다는 의미이므로 -1을 출력하고, 
• 그렇지 않다면 A[N]을 그대로 출력한다.