[백준] 2294 : 동전 2 - Java

• 백준 문제 URL

---

문제 요약

n가지 동전이 주어질 때(각 동전은 무한히 사용 가능), 합이 k원이 되도록 만들면서 사용한 동전 개수의 최솟값을 출력하는 문제다
만약 k원을 만들 수 없다면 -1을 출력한다.

---

핵심 아이디어(왜 DP인가?)

이 문제는 “현재 금액을 만들기 위해, 이전에 만들었던 금액의 최적해를 재사용”할 수 있어서 DP로 푸는 전형적인 유형이다
금액 j를 만들 때, 어떤 동전 c를 마지막에 1개 썼다고 가정하면 직전 상태는 j - c이므로 dp[j] = min(dp[j], dp[j - c] + 1) 형태로 갱신할 수 있다

---

DP 정의 & 점화식

dp 정의

• dp[x] = x원을 만들기 위한 최소 동전 개수 (만들 수 없으면 INF).

초기값

• dp[0] = 0 (0원을 만드는 데 동전 0개)
• 나머지는 큰 값(INF)로 채움.

점화식(무한 사용)

• 각 동전 c에 대해, 만들 수 있는 금액 j를 c부터 k까지 돌면서 갱신:
  dp[j] = min(dp[j], dp[j - c] + 1)

---

왜 반복문이 j = c부터 시작하나?

dp[j - c]를 참조해야 하므로 j가 c보다 작으면 j - c가 음수가 되어 말이 안 된다
또 j를 작은 금액부터 큰 금액으로(오름차순) 갱신하면, 같은 동전 c를 여러 번 사용하는 경우까지 자연스럽게 반영되어 “무한 사용” 조건을 만족한다.

---

INF를 100_001로 두는 이유

이 문제에서 k는 최대 10,000이라서, 최악의 경우(1원짜리가 있을 때) 필요한 동전 개수의 상한은 대략 10,000개 수준이다.
그래서 그보다 충분히 큰 값인 100_001 같은 수를 INF로 두면 “도달 불가능”을 안전하게 표현하면서 오버플로우도 피할 수 있다.

참고로 나의 경우 Integer.MAX_VALUE 로 제출하여 제출실패를 하였다.

---

전체 코드(제출용)

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[] coin = new int[n];
        for (int i = 0; i < n; i++) {
            coin[i] = Integer.parseInt(br.readLine());
        }

        int INF = 100_001;
        int[] dp = new int[k + 1];
        Arrays.fill(dp, INF);
        dp[0] = 0;

        for (int i = 0; i < n; i++) {
            int c = coin[i];
            for (int j = c; j <= k; j++) {
                dp[j] = Math.min(dp[j], dp[j - c] + 1);
            }
        }

        System.out.println(dp[k] == INF ? -1 : dp[k]);
    }
}