[Java][백준][골드 5] 동전 - 9084

이 문제는 다이나믹 프로그래밍(DP)의 아주 전형적이고 기초적인 문제로, 동전의 종류가 주어졌을 때 특정 금액을 만드는 모든 경우의 수를 구하는 문제다.

1. 문제 정보

• 문제 번호: 9084번
• 난이도: 실버 1 (Silver 1)
• 분류: 다이나믹 프로그래밍 (DP), 배낭 문제 (Knapsack)

 

2. 문제 설명

동전의 종류가 주어지고, 이 동전들을 사용하여 정해진 금액을 만드는 방법이 몇 가지인지 계산하는 프로그램을 작성해야 한다.

• 동전의 종류는 $1$원부터 $20$가지까지 있을 수 있다.
• 만들어야 하는 목표 금액은 최대 $10,000$원이다.
• 동전의 개수는 무제한으로 사용할 수 있다.

 

3. 풀이 전략 

이 문제는 전형적인 DP(Dynamic Programming) 문제입니다. 특정 금액 $j$를 만드는 방법의 수는 '이전 금액까지 구한 경우의 수'를 계속 누적해서 더해가는 방식으로 풀 수 있습니다.

1. DP 테이블 정의: dp[j]를 금액 j를 만드는 경우의 수라고 정의한다.
2. 초기값 설정: dp[0] = 1로 설정합니다. 아무 동전도 사용하지 않고 0원을 만드는 방법도 하나의 '경우'로 간주해야 다음 동전들이 들어올 때 제대로 계산이 시작된다.
3. 점점 더 큰 금액 채우기: 각 동전(num[k])을 순회하며, 해당 동전을 추가했을 때 만들 수 있는 금액들을 갱신한다.
   • 식: dp[j] = dp[j] + dp[j - 현재_동전_가치]
   • 예를 들어 2원짜리 동전으로 5원을 만드는 법은, 기존의 5원 만드는 법에 '3원을 만드는 법'에 2원을 하나 더한 경우를 추가하는 것과 같다.

 

4. 정답 코드 (Java)

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

public class Main {

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

        // 테스트 케이스 개수 입력
        int n = Integer.parseInt(br.readLine());

        for(int i = 0; i < n; i++){
            // 동전의 가짓수 입력
            int m = Integer.parseInt(br.readLine());

            int[] num = new int[m];
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < m; j++) {
                num[j] = Integer.parseInt(st.nextToken());
            }

            // 목표 금액 입력
            int c = Integer.parseInt(br.readLine());
            int[] dp = new int[c + 1];
            
            // 0원을 만드는 경우의 수는 1개 (아무것도 안 쓰기)
            dp[0] = 1;

            // 각 동전별로 DP 테이블 갱신
            for(int k = 0; k < m; k++){
                for(int j = num[k]; j <= c; j++){
                    // 현재 금액(j)에서 현재 동전 가치(num[k])를 뺀 금액의 경우의 수를 더해줌
                    dp[j] += dp[j - num[k]];
                }
            }

            // 최종 목표 금액 결과 출력
            System.out.println(dp[c]);
        }
    }
}

 

5. 핵심 포인트

• 중복 순열 방지: 동전을 하나씩 기준으로 잡고 내부 루프에서 금액을 갱신하기 때문에 동전의 순서가 다른 경우(예: 1+2, 2+1)를 중복해서 세지 않는다.
• dp[0] = 1의 의미: 동전 가치가 v일 때, dp[v] += dp[v-v] 즉, dp[0]의 값을 가져오게 됩니다. 이때 1이 더해져야 "해당 동전 하나만 쓰는 경우"가 최초로 카운트된다.
• 공간 복잡도: $10,000$ 크기의 배열 하나만 사용하므로 메모리 효율이 좋다.

 

마치며

동전 문제는 DP 공부를 시작할 때 반드시 거쳐가는 관문 같은 문제입니다. 이 문제의 로직을 이해하면 '배낭 문제(Knapsack Problem)'의 기초를 탄탄히 다질 수 있습니다.