[백준] 9084. 동전 / Java

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

9084번: 동전

---

문제 풀이

주어진 동전들로 목표 금액 M을 만들 수 있는 경우의 수를 찾아내는 문제이다.

일차원 dp 배열을 활용하여 각 금액에 대한 경우의 수를 갱신해나가는 방식으로 풀이할 수 있다.

dp[i] = j 일 때, 금액 i를 만들 수 있는 경우의 수는 j라는 의미이다.

 

예를 들어, 동전의 종류가 1, 2 세 가지가 있고 목표 금액이 10인 경우를 생각해보자.

먼저 1짜리 동전만 사용하는 경우에 대해 탐색해보자.

1(원)	2	3	4	5	6	7	8	9	10
1	1	1	1	1	1	1	1	1	1

 

다음은 2짜리 동전도 사용하는 경우를 탐색하는데, 이때 1짜리 동전을 사용했을 때의 결과를 활용한다.

점화식은 dp[i] = dp[i] + dp[i - coin] 이다. 단, i - coin = 0인 경우는 경우의 수가 1이므로 dp[0]의 값을 1로 초기화해준다.

1(원)	2	3	4	5	6	7	8	9	10
1	2	2	3	4	4	5	5	6	6

 

위와 같이 누적으로 각 동전 별로 모든 금액에 대해 탐색해나가면 최종적으로 dp[10] = 6을 답으로 구할 수 있다.

 

소스 코드

import java.io.IOException;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();

        for (int i = 0; i < T; i++) {
            int N = sc.nextInt();
            int[] coins = new int[N];

            for (int j = 0; j < N; j++) {
                coins[j] = sc.nextInt();
            }

            int M = sc.nextInt();

            System.out.println(solution(N, coins, M));
        }
    }

    static int solution(int N, int[] coins, int M) {
        int[] dp = new int[M+1];
        dp[0] = 1;

        for (int coin : coins) {
            for (int i = 1; i <= M; i++) {
                if (i >= coin) {
                    dp[i] = dp[i] + dp[i - coin];
                }
            }
        }

        return dp[M];
    }

}