[백준] 9084번 : 동전

문제

 

 

접근 방식

[백준] 2293번 : 동전 1

 

위의 문제와 입출력만 좀 다를 뿐 사실상 풀이가 같은 문제라 설명은 생략하겠다.

 

 

풀이

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 = Integer.parseInt(br.readLine());
        
        while (t-- > 0) {
            int n = Integer.parseInt(br.readLine());
            st = new StringTokenizer(br.readLine());
            int m = Integer.parseInt(br.readLine());
            int[] dp = new int[m + 1];
            
            dp[0] = 1;
            
            for (int i = 1; i <= n; i++) {
                int coin = Integer.parseInt(st.nextToken());
                
                for (int j = coin; j <= m; j++) {
                    dp[j] += dp[j - coin];
                }
            }
            
            sb.append(dp[m]).append("\n");
        }
        
        System.out.println(sb);
    }
}