⭕️[BOJ]2294 - 동전 2 (G5)

문제 링크

2294-동전 2

입력

첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000)
다음 n개의 줄에는 각각의 동전의 가치가 주어진다.
동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어질 수도 있다.

출력

첫째 줄에 사용한 동전의 최소 개수를 출력한다. 불가능한 경우에는 -1을 출력한다.

문제 풀이

동전1 과 아주 유사한 문제

위의 문제의 경우에는 dp를 가능한 가짓 수로 뒀지만,
이 문제의 경우에는 k를 만들 수 있는 동전의 최소갯수로 둬야한다.

점화식은 아래와 같다.
dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);

하지만 여기서 헤맸던 부분은 의외로 다른 부분이었는데

 Arrays.fill(dp, Integer.MAX_VALUE);
 System.out.println(dp[k] == Integer.MAX_VALUE ? -1 : dp[k]);

dp를 초기화해주는 부분과 마지막에 결과를 출력해주는 부분에서 100001 이 아닌 Integer.MAX_VALUE 로 처리하면 틀린다.
그것도 3%정도에서 틀린다
혹시나해서 바꿔보니 맞은 경우라 왜 틀렸는지 잘 모르겠다..

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        int[] coins = new int[n];
        int[] dp = new int[k + 1];

        for (int i = 0; i < n; i++) {
            coins[i] = Integer.parseInt(br.readLine());
        }

        // Arrays.fill(dp, Integer.MAX_VALUE);
        Arrays.fill(dp, 100001);
        dp[0] = 0;
        for (int i = 0; i < n; i++) {
            for (int j = coins[i]; j <= k; j++) {
                dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);
            }
        }
        // System.out.println(dp[k] == Integer.MAX_VALUE ? -1 : dp[k]);
        System.out.println(dp[k] == 100001 ? -1 : dp[k]);
    }
}