백준 2294: 동전2(Java)

💡 문제 요약

• n가지 종류의 동전을 가지고 있음
• 각각의 동전은 중복해서 사용할 수 있음
• 이 동전들을 이용해 총합이 k원이 되도록 할 때,
• 필요한 동전의 최소 개수를 구하라
• 불가능한 경우 -1을 출력하라

---

🧠 문제 분석

• 전형적인 동전 최소 개수 DP 문제
• 점화식 기반으로 1차원 DP 테이블을 구성하여 풀이

---

🔍 알고리즘 설계

1️⃣ DP 배열 정의

• dp[j] = j원을 만들기 위한 최소 동전 개수
• 초기값: dp[0] = 0, 나머지는 INF (큰 값)

2️⃣ 점화식

• 각 동전 금액 c에 대해
  dp[j] = min(dp[j], dp[j - c] + 1)

3️⃣ 최종 정답

• dp[k]가 INF이면 만들 수 없는 금액 → -1 출력
• 아니면 dp[k] 출력

---

✅ 코드 구현 (Java)

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

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 = k + 1;
        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] > k ? -1 : dp[k]);
    }
}

---

⏱️ 시간 복잡도

• O(N × K)
• N: 동전 종류 수 (최대 100), K: 금액 (최대 10,000)
• 10^6 이내이므로 충분히 가능

---

📌 정리

• 각 금액마다 최소 동전 개수를 메모이제이션 방식으로 저장
• 모든 동전으로 K까지 누적 계산하여 최솟값을 구하는 방식
• 2중 for문이지만 내부 연산이 매우 작고 빠름