[Java] BOJ 14916 거스름돈

14916번: 거스름돈

---

정답 코드

• 예외 케이스 처리 후 DP활용 풀이
• 최소값을 구하는 문제임을 생각하고 처리하기

import java.io.*;
import java.util.*;

public class Main {

    static BufferedReader br;
    static BufferedWriter bw;
    static StringTokenizer st;
    static int N;
    static int[] arr;

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        arr = new int[N + 1];
        Arrays.fill(arr, Integer.MAX_VALUE);
        if (N == 2) {
            arr[2] = 1;
        } else if (N == 4) {
            arr[4] = 2;
        } else if (N == 5) {
            arr[5] = 1;
        } else if (N > 5) {
            arr[2] = 1;
            arr[4] = 2;
            arr[5] = 1;
            for (int i = 6; i <= N; i++) {
                arr[i] = Math.min(arr[i - 2], arr[i - 5]) + 1;
            }
        }

        System.out.println(arr[N] == Integer.MAX_VALUE ? -1 : arr[N]);
    }
}​