백준 2624 "동전 바꿔주기" (JAVA)

🔍 문제링크

https://www.acmicpc.net/problem/2624

---

📌 문제 요약

• 목표 금액 n을 만들기 위해 k가지 종류의 동전이 주어진다.
• 각 동전은 개수 제한이 있음.
• 주어진 동전을 사용하여 목표 금액을 만드는 방법의 수를 구하는 문제

---

🛠 풀이 및 알고리즘

1️⃣ DP(동적 계획법) 활용

• dp[i] : i원을 만드는 경우의 수
• 배낭 문제와 비슷한 접근 방식을 사용하여 동전의 개수 제한을 고려

2️⃣ 점화식 유도

• 기본적인 동전 문제는 개수 제한 없이 무한히 사용할 수 있는 경우
  → dp[j] += dp[j - amount]
• 그러나 이 문제는 개수 제한이 존재
  → s개의 동전을 사용하는 경우를 고려해야 함

for (int s = 1; s <= cnt; s++) {
    if (j - s * amount < 0) break; // 금액 초과시 종료!
    dp[j] += dp[j - s * amount];
}

• dp[j]는 현재 금액 j를 만들기 위해 s개의 동전을 사용했을 때 경우의 수를 누적

---

💡 코드

public class Baekjoon_2624 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); // 목표 금액
        int k = sc.nextInt(); // 동전 종류수
        int[] dp = new int[n + 1];
        dp[0] = 1;
        for (int i = 0; i < k; i++) {
            int amount = sc.nextInt(); // 동전 가치
            int cnt = sc.nextInt();    // 동전 개수

            for (int j = n; j >= 0; j--) { // 큰 금액부터 처리
                for (int s = 1; s <= cnt; s++) {
                    if (j + s * amount > n) { // 금액 초과 시 종료
                        break;
                    }
                    dp[j + s * amount] += dp[j];
                }
            }
        }

        System.out.println(dp[n]);
    }
}

---

🏆 시간 복잡도 분석

• k개의 동전을 탐색 (O(K))
• 각 동전에 대해 n원을 만들기 위한 반복문 (O(N))
• 개수 제한(cnt)을 고려한 내부 반복문 (O(C))
• 총 시간 복잡도: O(K * N * C) (C: 동전 개수 제한)
• N ≤ 10,000, K ≤ 100, C <=1000이므로  최악의 경우 O(K * N * C) = O(1,000,000,000) 이지만, break로 최적화했기 때문에 통과