[JAVA] 백준 q9084 - 동전

9084번: 동전

---

의식의 흐름

dfs로 풀면 되지않나..? > 시간 초과
0~M까지 만들 수 있는 경우의 수를 담아놓자 > 성공

풀이 과정

1. 테스트케이스의 수(T)를 입력 받는다.
2. 동전의 가지 수(N)를 입력 받는다.
3. N가지 동전의 금액을 배열(coins)에 담는다.
4. 만들어야 할 금액(M)을 입력 받는다.
5. 각 합을 만들 수 있는 경우의 수를 담을 배열(dp)을 생성한다.
- dp[j] = 동전의 합이 j인 경우의 수
- dp[0] = 1로 고정 (j - i번째 동전 값 == 0인 경우를 위해)
6. 각 합에 대한 경우의 수를 구한다.
ex) coin = 5, j = 8인 경우, dp[j] = (이전까지 구한 8을 만들 수 있는 경우의 수) + (3을 만들 수 있는 경우의 수)

dp[j] += dp[j-coin];

 

7. 2번~6번 과정을 T만큼 반복한다.
8. 결과를 출력한다.

 

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
    public static int T, N, M;
    public static int[] coins; // 동전 금액
    public static int[] dp; // dp[i] = 동전으로 dp[i] 만들 수 있는 경우의 수

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        T = Integer.parseInt(br.readLine()); // 테스트케이스 수
        while(T-->0){
            N = Integer.parseInt(br.readLine()); // 동전의 가지 수

            coins = new int[N];
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int i=0;i<N;i++){
                coins[i] = Integer.parseInt(st.nextToken());
            }

            M = Integer.parseInt(br.readLine()); // 만들어야 할 금액
            dp = new int[M+1]; // dp[i] = 동전 합이 i인 경우의 수
            dp[0] = 1;
            for(int i=0;i<N;i++){
                int coin = coins[i];
                for(int j=coin;j<=M;j++){
                    dp[j] += dp[j-coin];
                }
            }

            bw.write(Integer.toString(dp[M])+"\n");
        }
        bw.flush();

        br.close();
        bw.close();
    }
}