OJ
[BOJ] 9084 동전 (JAVA)
P3PP4
2023. 4. 24. 10:00
https://www.acmicpc.net/problem/9084
9084번: 동전
우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는
www.acmicpc.net
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringBuilder sb = new StringBuilder();
static StringTokenizer st;
static int T, N, M;
static int[] value;
static int[][] dp;
public static void main(String[] args) throws Exception {
T = Integer.parseInt(br.readLine());
for (int tc = 0; tc < T; tc++) {
N = Integer.parseInt(br.readLine());
value = new int[N + 1];
st = new StringTokenizer(br.readLine(), " ");
for (int i = 1; i <= N; i++) {
value[i] = Integer.parseInt(st.nextToken());
}
M = Integer.parseInt(br.readLine());
dp = new int[N + 1][M + 1];
for (int i = 1; i <= N; i++) {
if (value[i] <= M) dp[i][value[i]] = 1;
for (int j = 1; j <= M; j++) {
dp[i][j] = dp[i][j] + dp[i - 1][j] + (value[i] <= j ? dp[i][j - value[i]] : 0);
}
}
sb.append(dp[N][M]).append("\n");
}
System.out.print(sb);
}
}