[백준] 14916. 거스름돈

문제 링크

[백준] 14916. 거스름돈

풀이 과정

동적 계획법을 사용해 문제를 풀었습니다.

int[] dp = new int[100001];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[2] = dp[5] = 1;
dp[4] = 2;

dp[i] 는 i원을 거슬러주기 위한 동전의 최소 개수를 의미합니다. 2원과 5원짜리 동전만 사용할 수 있으므로 둘의 최소 개수 dp[2]와 dp[5]를 1로 설정합니다.

4원은 2원짜리 두 개로 거슬러 주는 것이 최적의 방법이므로, dp[4]는 2로 설정합니다. dp 배열의 4번째 요소, 즉 dp[4]도 미리 초기화해주는 이유는 아래에서 for 반복문을 인덱스 6부터 돌기 위해서입니다.

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

i원을 거슬러주는 방법은 두 가지입니다.

1. (i - 2)원을 거슬러줄 동전 조합에 2원짜리 동전을 하나 더 추가
2. (i - 5)원을 거슬러 줄 동전 조합에 5원짜리 동전을 하나 더 추가

따라서, dp[i - 2]와 dp[i - 5] 둘 중 더 작은 값에 1을 더한 값을 dp[i]에 저장합니다.

코드

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();
        int[] dp = new int[100001];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[2] = dp[5] = 1;
        dp[4] = 2;

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

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