[백준_JAVA_알고리즘] 14916 거스름돈 #DP

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(bufferedReader.readLine());
        int[] dp = new int[n + 1];

        if (n < 1) {
            System.out.println(-1);
            return;
        }
        dp[1] = -1;
        if(n >= 2) dp[2] = 1;
        if(n >= 3) dp[3] = -1;
        if(n >= 4) dp[4] = 2;
        if(n >= 5) dp[5] = 1;

        /*
        dp[6] = 3;
        dp[7] = 2;
        dp[8] = 4;
        dp[9] = 3;
        dp[10] = 2;
        dp[11] = 4;
        dp[12] = 3;
        dp[13] = 5;
        dp[14] = 4;
        */

        if(n >= 6){
            for (int i = 6; i <= n; i++) {
                if (dp[i-2] == -1 && dp[i-5] == -1) {
                    dp[i] = -1;
                } else if (dp[i-2] == -1) {
                    dp[i] = dp[i-5] + 1;
                } else if (dp[i-5] == -1) {
                    dp[i] = dp[i-2] + 1;
                } else {
                    dp[i] = Math.min(dp[i-2], dp[i-5]) + 1;
                }
            }
        }
        System.out.println(dp[n]);
    }
}

 

2원짜리와 5원짜리로 거스름돈을 주어야 하기 때문에 dp[2] = dp[5] = 1로 설정합니다.

dp[1], dp[3]은 거스름돈으로 줄 수 없기 때문에 -1로 설정합니다.

dp[4]의 경우 2원짜리 2개로 줄 수 있기 때문에 dp[4] = 2로 설정합니다.

 

현재 위치(i)에서 2를 뺀 위치와 5를 뺀 위치의 값을 확인합니다.
두 위치 모두 -1이면 현재 위치도 -1이 됩니다.
i-2 위치가 -1이면 i-5 위치의 값에 1을 더합니다.
i-5 위치가 -1이면 i-2 위치의 값에 1을 더합니다.
둘 다 -1이 아니면, 두 값 중 최소값에 1을 더합니다.

 

.

.

.

 

문제는 아래에서 확인할 수 있습니다.

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