[백준 9084] 동전

 

풀이

이 문제는 동전으로 금액 M을 만들 수 있는 모든 경우를 구하는 문제이다. 동전의 금액은 모두 다르며, 사용할 수 있는 동전의 개수에는 제한이 없다.

 

2차원 dp[][]를 채워나가는데 크게 두개의 상황으로 나뉜다.

1. 현재 동전을 사용하지 않는 경우
2. 현재 동전을 사용하는 경우

현재 동전을 사용하지 않는 경우는 이전의 동전까지 고려했을때 금액 M을 만드는 경우의 수와 동일하므로 점화식은 아래와 같다.

dp[n][m] = dp[n-1][m]

 

현재 동전을 사용하는 경우에는 현재 동전을 사용하지 않는 경우 + 현재 동전을 사용하는 경우 를 더해주면 된다. 여기서 현재 동전을 사용한다는 것은 만들어야 하는 금액 M이 있다면 (M-현재 동전의 금액)이 만들어야 하는 금액이 된다. 즉, 현재 동전은 무조건 선택해야하므로 금액을 빼주어야 한다.

 

그리고 이미 dp에는 현재 동전을 1개 사용한 경우, 2개 사용한 경우도 포함되어 있기 때문에 누적으로 합을 구해주면 된다.

 

만약, 현재 동전의 가짓수가 5개이고, 금액이 각각 1, 2, 3, 4, 5 라고 해보자.

그렇다면 dp의 초기 상태는 아래와 같다.

 

만약, 두번째 동전을 고려하는 단계에서는 아래와 같다. 분홍색으로 칠한 부분을 보면 두번째 동전을 한개 사용한 경우의 수가 dp에 저장되어 있음을 알 수 있다.

 

 

구현

 

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

public class Solution_for_9084 {
    static int T, N, M;

    static int[] coins;
    static int[][] dp;

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

        T = Integer.parseInt(st.nextToken());

        for (int t = 0; t < T; t++) {
            // 동전의 가지 수 입력받기
            st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            
            // 동전의 금액 입력받기
            coins = new int[N+1];
            st = new StringTokenizer(br.readLine());
            for (int n = 1; n < N+1; n++) {
                coins[n] = Integer.parseInt(st.nextToken());
            }

            // 만들어야 할 금액 입력받기
            st = new StringTokenizer(br.readLine());
            M = Integer.parseInt(st.nextToken());

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

            for (int n = 1; n < N+1; n++) {
                
                int amount = coins[n];
                
                for (int m = 0; m < M+1; m++) {
                    // 현재 동전을 사용하지 않는 경우
                    dp[n][m] = dp[n-1][m];

                    // 현재 동전을 사용하는 경우
                    if ((m - amount) < 0) continue;

                    dp[n][m] += dp[n][m - amount];
                }
            }

            sb.append(dp[N][M] + "\n");
        }

        System.out.println(sb);
    }
}