[백준][Java] 9084 - 동전

목차

문제 정보

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

9084번: 동전

난이도 : G5

유형 : DP, 배낭문제

 

동일문제

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

3067번: Coins

---

문제 풀이

배낭문제 유형의 기본문제

이 문제의 공간복잡도는 M이고

동전 종류마다 1 ~ M까지 몇 개씩 사용할 수 있는지 체크하면 된다.

 

점화식

(dp[0] = 1 초기화)

dp[i] = dp[i] + dp[i- coin종류]

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    private int T, N, M;
    private int[] coins;
    private int[] dp;

    public void solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        T = Integer.parseInt(br.readLine());
        while (T-- > 0) {
            N = Integer.parseInt(br.readLine());
            coins = new int[N];

            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[0] = 1;

            for (int coin : coins) {
                for (int i = 0; i <= M; i++) {
                    if (i - coin >= 0) {
                        dp[i] += dp[i - coin];
                    }
                }
            }
            sb.append(dp[M]).append('\n');
        }
        System.out.print(sb);
    }

    public static void main(String[] args) throws IOException {
        new Main().solution();
    }
}