[자바]백준 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을 출력한다.

예제

예제

알고리즘 분류

• 수학
• 다이나믹 프로그래밍
• 그리디 알고리즘

문제설명

위의 문제 설명은 간단하다.

5원과 2원 만을 사용하여 최소의 개수로 주어진 n원을 만들때 최소의 수를 구하면 된다.

해설

해당 문제는 간단하게 5원의 개수를 구하고 남은 금액을 2원으로 계산하면 되겠다 생각하다가는 아래와 같은 이유로 틀리게 된다. 

 

• n = 16 이라 가정하자
• 5원을 먼저 계산하면, 5원 3개로 15원을 만들고 1원이 남는다.
• 1원을 2원으로 계산하려고 하면 계산이 안된다.

1원부터 n원까지 순서대로 최소의 개수를 구해 주면 된다.

왜? 순서대로 다 구해줘야 하는가?

16원으로 예시를 들어보겠다.

 

• 5 + 5 + 2 + 2 + 2
• 2 + 2 + 2 + 2 + 2 + 2
• 5 + 5 + 5 + 2 (x)

이런 식으로 하나하나 구해볼 수도 있다. 하지만 n이 100,000이 되면 이걸 하나하나 구할 수 있을까?

그럼 시간복잡도가 오버해서 시간초과가 나올 것이다.

 

그렇다면 방법은 하나다 거슬러 올라가는 방법을 사용해야한다.

 

1. 16원이면 14원 혹은 9원의 최솟값에 1개를 더하는 것이다.
2. 그럼 14원의 최솟값 9원의 최솟값은 어떻게 아느냐?
3. 그래서 1원부터 n원까지 최솟값을 처음부터 구해서 마지막 n원의 최솟값을 파악하는 것이다.

결론

n원의 2원과 5원의 최소 조합의 개수는

 

1. (n - 2) 원 에서의 최소 조합의 개수 
2. (n - 5) 원 에서의 최소 조합의 개수

둘 중에 가장 작은 값에 더하기 1을 해주면 n원의 최소 조합의 개수가 나온다.

 

글로만 설명하려니 잘 안되는데, 추후에 이미지를 만들어서 첨부하겠다.. 

바로 코드를 보겠다.

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        final int LNF = Integer.MAX_VALUE;

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

        int[] arr = new int[n + 1 + 6];
        arr[0] = LNF;
        arr[1] = LNF;
        arr[2] = 1;
        arr[3] = LNF;
        arr[4] = 2;
        arr[5] = 1;

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

        System.out.println(arr[n] == LNF ? -1 : arr[n]);
        br.close();
    }
}

코드 설명

필요한 부분만 설명하겠다.

arr배열의 길이를 n + 1 + 6으로 잡은 이유

 

• n + 1은 n개를 구해야 하니까 당연히 n + 1로 넣어줘야 한다.
• +6을 해준 이유는 0부터 5까지 직접 값을 넣어주기 위해서 인데 +6을 해줘야 에러를 발생시키지 않는다.
• 어차피 n번째를 구하면 되기 때문에 n 이상 6개 더 최솟값을 구한다 해서 문제가 되지 않는다.

0, 1, 3을 MAX_VALUE로 넣어주고 2와 4와 5는 다른 값을 넣어준 이유

 

• 0, 1, 3 은 개수를 구할 수 없어서 LNF로 넣어준 것이다.
• 문제에서 구할 수 없으면 -1을 출력하라고 해서 -1을 넣어주게 되면 아래와 같이 조건문이 추가되어 좀 더 복잡해진다.

for (int i = 6; i < arr.length; i++) {
	// 조건문을 해주지 않으면 -1이 최소값이 -1 + 1 = 0이 출력된다.
	if (arr[i - 2] == - 1) { 
    	arr[i] = arr[i - 5] + 1;
    } else if (arr[i - 5] == - 1) {
    	arr[i] = arr[i - 2] + 1;
    } else {
    	arr[i] = Math.min(arr[i - 2], arr[i - 5]) + 1;
    }
}

• 2, 4, 5는 구할 수 있는 최솟값을 넣어준 것이다.