[백준] 9084. 동전

문제 링크

[백준] 9084. 동전

풀이 과정

다이나믹 프로그래밍 문제입니다.

동전의 각 금액은 오름차순으로 정렬되어 주어집니다. 따라서, 적은 금액의 동전 값을 시작으로 목표 금액 M원을 만들 수 있는 경우의 수를 메모이제이션 배열에 누적시키며 최종 개수를 구할 수 있게 됩니다. 아래 예시를 통해 설명하도록 하겠습니다.

예를 들어, 2, 3, 4원의 세 개의 동전으로 총 10원을 만드는 경우의 수는 위와 같이 5개입니다. 이를 메모이제이션을 적용해 구해보도록 하겠습니다.

메모이제이션 배열 dp는 0번째 요소를 제외하고 0으로 초기화 되어있습니다.

• dp[i]는 주어진 동전들을 사용해 i원을 만들 수 있는 경우의 수를 의미합니다. 예를 들어 dp[10]이 5면, 5개의 방법으로 10원을 만들 수 있음을 의미합니다.
• dp[0]은 초기에 1로 세팅합니다. 누적시킨다는 개념으로 문제를 접근했을 때, 2원짜리 동전만을 사용해 2원을 만드는 방법은 한 가지입니다. 아무 동전도 사용하지 않은 상태, 즉 0원인 상태에서 2원짜리 동전을 하나 사용해 만들 수 있습니다.
• 이를 수식으로 표현하자면 dp[2] += dp[2-2] 가 됩니다. 0번째 요소, 즉 dp[0]을 사용해 개수를 세야 하므로, dp[0]을 1로 초기화 합니다.

먼저 2원짜리 동전만을 이용해 각 금액을 만들 수 있는 경우의 수를 구해봅니다. 2원짜리 동전으로는 2원, 4원, 6원, 8원, 10원 총 다섯 개의 금액을 완성시킬 수 있습니다. 누적시킨다는 개념을 통해, dp[2] += dp[0] 으로 1이 되며, 이와 동일한 방법 4, 6, 8, 10원의 개수를 갱신할 수 있습니다.

3원짜리 동전도 사용했을 때 각 금액을 만들 수 있는 경우의 수는 위와 같습니다. 3원짜리 동전 하나만을 이용해 3원을 만들 수 있으므로, dp[3] = 1 이 됩니다. 5원의 경우, 이전에서 봤을 때 2원짜리 동전만으로는 만들 수 없지만, 3원짜리 동전이 새로 추가됨으로써 2+3 = 5원을 만들 수 있게 됩니다.

4원짜리 동전까지 사용했을 때, 즉 모든 동전을 이용해 각 금액을 만들 수 있는 경우의 수는 위와 같습니다. dp[10]은 기존의 경우의 수 2 값에 6원을 만드는 경우의 수 3을 더해 5가 되는 것을 확인할 수 있습니다.

int[] dp = new int[M + 1];
dp[0] = 1;

for (int i = 0; i < N; i++) {
    for (int j = coin[i]; j <= M; j++) {
        dp[j] += dp[j - coin[i]];
    }
}

위 과정을 코드로 나타내면 다음과 같습니다.

• 먼저, 위와 같이 메모이제이션을 위한 dp 배열을 선업합니다. N가지 동전으로 만들어야 될 최종 금액 M을 수용할 수 있도록, M+1만큼의 크기로 선언해줍니다.
• 또한, dp[0]은 1로 초기화해줍니다.
• 이제 인덱스 j를 각 동전의 값을 시작으로 M까지 순회를 하며, dp[j]를 누적시킵니다.

코드

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int TC = sc.nextInt();

        for (int tc = 1; tc <= TC; tc++) {
            int N = sc.nextInt();
            int[] coin = new int[N];
            for (int i = 0; i < N; i++) coin[i] = sc.nextInt();
            int M = sc.nextInt();
            int[] dp = new int[M + 1];
            dp[0] = 1;

            for (int i = 0; i < N; i++) {
                for (int j = coin[i]; j <= M; j++) {
                    dp[j] += dp[j - coin[i]];
                }
            }

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