/
BAEKJOON 9084
34 lines (32 loc) · 1.34 KB
/
BAEKJOON 9084
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
static int N, M;
static int[] coin; //동전 몇원짜리 있는지 저장
static int[] dp; // dp 배열
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
for (int t = 1; t <= T; t++) {
N = Integer.parseInt(br.readLine());
coin = new int[N];
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
coin[i] = Integer.parseInt(st.nextToken());
}
M = Integer.parseInt(br.readLine());
dp = new int[M + 1];
dp[0] = 1; // 해당 값을 자기 자신으로 만들수 있는지 체크하기위해 초기값을 넣어줌
// 현재 값 - 자기값이 0 이면 자기 자신으로 만들수 있음
for (int i = 0; i < N; i++) {
for (int j = 1; j <= M; j++) {
if(j - coin[i] >= 0) // 0보다 작은 경우는 현재 값이 코인값보다 작은 경우니깐 제외
dp[j] += dp[j - coin[i]]; // 1차원 배열에 값이 계속 쌓이는 방식 현재 값에 지금 코인 값 뺀 값만들수 있는 갯수 더해주는 방식
}
}
System.out.println(dp[M]); // 마지막값이 최종값
}
}
}