[B3067][Coins][java]

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

 

 

풀이

// dp[25], arr = 5, 7, 9

// 5원일 때,
// dp[25] <- dp[20] <- dp[15] <- dp[10] <- dp[5] <- dp[0]
// dp[24] <- dp[19] <- dp[14] <- dp[9] <- dp[4]

// 5 : dp[5] += dp[0], dp[6] += dp[1], dp[7] += dp[2]
// 7 : dp[7] += dp[0], dp[8] += dp[1], dp[9] += dp[2]

 

 

코드

package com.example.algorithm.study.week13;

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

public class B3067_Coins {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        while (t-- > 0) {
            int n = Integer.parseInt(br.readLine());
            int[] arr = Arrays.stream(br.readLine().split(" "))
                    .map(Integer::parseInt)
                    .mapToInt(Integer::intValue).toArray();
            int cost = Integer.parseInt(br.readLine());
            System.out.println(solution(n, arr, cost));
        }
    }

    static int solution(int n, int[] arr, int cost) {
        int[] dp = new int[10001];
        dp[0] = 1;
        for (int i = 0; i < n; i++) {
            for (int j = arr[i]; j <= cost; j++) {
                dp[j] += dp[j - arr[i]];
            }
        }
        return dp[cost];
    }
}