[백준] BOJ_9084 - 동전

이종찬·2026년 2월 3일

baekjoon

1. 문제 정보

문제 요약: 우리나라 화폐 단위와 달리, 가지 종류의 동전이 주어집니다. 이 동전들을 사용하여 특정 금액 을 만들 수 있는 모든 경우의 수를 구하는 문제입니다. (동전의 개수는 무제한입니다.)
난이도: Gold 5
링크: 백준 9084번 - 동전

2. 접근 방식

1) 문제의 본질: 순열 vs 조합

이 문제의 핵심은 "순서가 다른 구성을 같은 것으로 볼 것인가?" 입니다.
예를 들어 3원을 만들기 위해 1원, 2원을 쓴다면:

1원 + 2원
2원 + 1원

위 두 가지를 다르게 세면 순열, 하나로 본다면 조합입니다. 문제에서는 "동전의 구성을 따진다"고 했으므로, 순서만 다른 것은 중복으로 처리하여 한 가지 경우로 세어야 합니다. 이를 위해 반복문(Loop)의 순서를 전략적으로 설계해야 합니다.

2) 알고리즘 설계: 배낭 문제 (Knapsack)

가장 직관적인 방법은 DFS(백트래킹)지만, 이 최대 10,000이고 시간 제한이 있으므로 지수 시간 복잡도를 가지는 재귀는 적합하지 않습니다. 따라서 중복된 하위 문제(Overlapping Subproblems)를 해결하는 DP를 사용합니다.

중복을 방지하기 위한 루프 설계의 핵심은 다음과 같습니다:

Bad Loop (순열): 금액을 기준으로 먼저 돌고, 내부에서 동전을 돌리면 1+2와 2+1이 중복 카운팅됩니다.
Good Loop (조합): 동전을 기준으로 먼저 돌고, 내부에서 금액을 채워나가면, "1원만 썼을 때", "1원과 2원을 썼을 때" 처럼 동전이 추가되는 흐름이 강제되어 중복이 자연스럽게 제거됩니다.

3) 점화식

$DP[i]$ 를 금액 를 만드는 경우의 수라고 정의합니다.

어떤 동전의 가치가 라고 할 때, 금액 를 만드는 방법은 "이미 원을 만든 경우의 수에 원 동전 하나를 얹는 것"과 같습니다.

초기값: (0원을 만드는 경우의 수는 '아무것도 안 내는' 1가지입니다. 그래야 점화식이 누적됩니다.)
범위: 동전의 가치 부터 목표 금액 까지 순회합니다.

3. 코드 구현

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

class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int T, N, M;
    static int[] coin;

    public static void main(String[] args) throws IOException {
        StringBuilder sb = new StringBuilder();
        T = Integer.parseInt(br.readLine()); // 테스트 케이스 개수
        
        for (int i = 0; i < T; i++) {
            N = Integer.parseInt(br.readLine()); // 동전의 가지 수

            coin = new int[N];
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++)
                coin[j] = Integer.parseInt(st.nextToken());

            M = Integer.parseInt(br.readLine()); // 목표 금액

            int answer = solv();
            sb.append(answer).append('\n');
        }

        System.out.println(sb);
    }

    private static int solv() {
        // DP[i]: 금액 i를 만드는 경우의 수
        int[] dp = new int[M + 1];
        
        // 초기값 설정: 0원을 만드는 방법은 1가지 (아무 동전도 선택하지 않음)
        dp[0] = 1;

        // Outer Loop: 동전 (중복 방지 핵심)
        for (int c : coin) {
            // Inner Loop: 금액
            for (int i = c; i <= M; i++) {
                dp[i] += dp[i - c];
            }
        }

        return dp[M];
    }
}