[백준 / 골드5] 9084 동전 (Java)

문제 보기

사용한 것

• 동전 조합의 수를 구하기 위한 bottom-up

풀이 방법

• dp[0]을 1로 초기화
• 현재 동전을 사용한 경우를 계속해서 더해줌 (dp[k] += dp[k - coin])

코드

public class Main {

    public static void main(String[] args) throws IOException {
        // 초기화
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
        int t, n, m, coin;
        int[] coins, dp;
        t = Integer.parseInt(br.readLine());
        for (int i = 0; i < t; i++) {
            n = Integer.parseInt(br.readLine());
            coins = new int[n];
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                coins[j] = Integer.parseInt(st.nextToken());
            }
            m = Integer.parseInt(br.readLine());

            // DP
            dp = new int[m + 1];
            dp[0] = 1;
            for (int j = 0; j < n; j++) {
                coin = coins[j];
                for (int k = coin; k <= m; k++) {
                    dp[k] += dp[k - coin];
                }
            }
            sb.append(dp[m]).append(lineSeparator());
        }

        System.out.println(sb);
    }
}