[伯俊]9084硬貨(銀1)

に答える

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

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int tc = Integer.parseInt(br.readLine());
		StringBuilder sb = new StringBuilder();
		for(int t=0; t<tc; t++) {
			int result = 0;
			int N = Integer.parseInt(br.readLine());
			StringTokenizer st = new StringTokenizer(br.readLine());
			int[] coins = new int[N];
			int money = 0;
			
			
			for(int i=0; i<N; i++) {
				coins[i] = Integer.parseInt(st.nextToken());
			}//coins input
			money = Integer.parseInt(br.readLine());//만들어야하는 결과물
			
			int[] dp = new int[10001];
			
			dp[0] = 1;
			
			for(int i=0; i<N; i++) {
				for(int j=coins[i]; j<=money; j++) {
					dp[j] += dp[j-coins[i]];
				}
			}
			result = dp[money];
			
			sb.append(result+"\n");

		}
		System.out.println(sb);
	}

}