백준 9084번
https://www.acmicpc.net/problem/9084
n
= coinIndex, m
= amount
최종적으로 0원을 만드는 방법 -> 더 이상 동전을 사용할 필요가 없는 경우) 하나의 유효한 조합으로 간주된다.
private static int topDown(int n, int m) {
if (m == 0) return 1;
if (n <= 0 || m < 0) return 0; // 사용할 수 있는 동전이 없거나, 금액을 만들 수 없는 경우
if (memo[n][m] != -1) return memo[n][m];
// 현재 선택된 동전을 사용하는 경우 + 사용하지 않는 경우
memo[n][m] = topDown(n, m - coins[n - 1]) + topDown(n - 1, m);
return memo[n][m];
} // End of topDown()
// 현재 선택된 동전을 사용하는 경우 + 사용하지 않는 경우 memo[n][m] = topDown(n, m - coins[n - 1]) + topDown(n - 1, m);
n
이 감소 하지 않는 이유는 동전의 사용횟수가 정해져 있지 않기 때문에 같은 동전을 계속 사용하는 조건, 동전을 사용하지 않아서 다음으로 넘어가는 n - 1
의 선택지가 있다.
import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
// input
private static BufferedReader br;
// variables
private static int N, M;
private static int[][] memo;
private static int[] coins;
public static void main(String[] args) throws IOException {
br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int t = Integer.parseInt(br.readLine());
while (t-- > 0) {
input();
bw.write(solve());
}
bw.close();
} // End of main()
private static String solve() {
StringBuilder sb = new StringBuilder();
sb.append(topDown(N, M)).append('\n');
return sb.toString();
} // End of solve()
private static int topDown(int n, int m) {
if (m == 0) return 1;
if (n <= 0 || m < 0) return 0; // 사용할 수 있는 동전이 없거나, 금액을 만들 수 없는 경우
if (memo[n][m] != -1) return memo[n][m];
// 현재 선택된 동전을 사용하는 경우 + 사용하지 않는 경우
memo[n][m] = topDown(n, m - coins[n - 1]) + topDown(n - 1, m);
return memo[n][m];
} // End of topDown()
private static void input() throws IOException {
N = Integer.parseInt(br.readLine());
coins = new int[N + 1];
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
coins[i] = Integer.parseInt(st.nextToken());
}
M = Integer.parseInt(br.readLine());
memo = new int[N + 1][M + 1];
for (int i = 0; i <= N; i++) {
Arrays.fill(memo[i], -1);
}
} // End of input()
} // End of Main class
import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
// input
private static BufferedReader br;
// variables
private static int N, M;
private static int[][] memo;
private static int[] coins;
public static void main(String[] args) throws IOException {
br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int t = Integer.parseInt(br.readLine());
while (t-- > 0) {
input();
bw.write(solve());
}
bw.close();
} // End of main()
private static String solve() {
StringBuilder sb = new StringBuilder();
sb.append(bottomUp()).append('\n');
return sb.toString();
} // End of solve()
private static int bottomUp() {
// 기저조건
for (int i = 0; i <= N; i++) {
memo[i][0] = 1;
}
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
// 현재 동전의 가치가 j보다 크면, 이 동전은 사용할 수 없다.
if (coins[i - 1] > j) {
memo[i][j] = memo[i - 1][j];
} else {
// 현재 동전을 사용하지 않는 경우 + 현재 동전을 사용하는 경우
memo[i][j] = memo[i - 1][j] + memo[i][j - coins[i - 1]];
}
}
}
return memo[N][M];
} // End of bottomUp
private static void input() throws IOException {
N = Integer.parseInt(br.readLine());
coins = new int[N + 1];
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
coins[i] = Integer.parseInt(st.nextToken());
}
M = Integer.parseInt(br.readLine());
memo = new int[N + 1][M + 1];
} // End of input()
} // End of Main class