🎯 문제 요약

목표: k원을 만드는 데 필요한 최소 동전 개수

우리가 가진 선택지는
“각 금액 i원을 만들기 위해 어떤 동전을 쓸 것인가”
이걸 모든 경우 중 최소값으로 정하는 것

1️⃣ 큰 문제 → 작은 문제로 쪼개기

예를 들어 i원을 만들고 싶다면?

그럼 i원을 만들기 위한 마지막 선택은
“마지막으로 사용한 동전이 무엇인가?”로 나눌 수 있다.

예를 들어:

i = 6, coins = {1, 3, 4}라면
마지막으로 쓴 동전이

1원이면 → 이전엔 5원을 만들어야 함
3원이면 → 이전엔 3원을 만들어야 함
4원이면 → 이전엔 2원을 만들어야 함

즉,

6원을 만드는 최소 동전 수 =

min(
5원을 만드는 최소 동전 수 + 1,
3원을 만드는 최소 동전 수 + 1,
2원을 만드는 최소 동전 수 + 1
)

2️⃣ 수식으로 표현

이걸 일반화하면:

dp[i] = min(dp[i - coin] + 1) for all coin ≤ i

dp[i - coin] → i - coin원을 만들 때 필요한 최소 동전 개수

+1 → 그 뒤에 coin 하나를 더 써서 i원을 만든 것

그 중 가장 적은 경우(min)를 선택

이게 바로 dp[i] = Math.min(dp[i], dp[i - coin] + 1)이 나오는 이유!

---

정답 코드

package algo.ct.M11;

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

public class BOJ_2294_동전2_G5 {
    static int n, k;
    static int[] coins;

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

        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
        coins = new int[n];

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

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

        for (int coin : coins) {
            for (int i = coin; i <= k; i++) {
                dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
        }

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