[ 백준 ] 9084 동전

📌 Problem

N개의 서로 다른 가치의 동전들이 오름차순으로 주어진다. 목표한 금액을 주어진 동전들을 사용하여 만들 수 있는 경우의 수를 구하면 된다. 동전들은 중복으로 사용할 수 있으나 순서와 상관없이 동일한 구성이면 같은 경우로 생각한다. 배낭문제를 통해 해결할 수 있다.

📌 Code

int T = Integer.parseInt(reader.readLine());
while (T-- > 0) {
    int numberOfCoins = Integer.parseInt(reader.readLine());
    int[] coins = Arrays.stream(reader.readLine().split(" "))
            .mapToInt(Integer::parseInt).toArray();
    int targetMoney = Integer.parseInt(reader.readLine());

    int[] dp = new int[targetMoney + 1];
    dp[0] = 1;
    for (int coin : coins)
        for (int c = coin; c <= targetMoney; c++) dp[c] += dp[c - coin];

    result.append(dp[targetMoney]).append('\n');
}