문제
n가지 종류의 동전이 있고, 각 동전은 여러 개 사용 가능하다. 이 동전들을 사용하여 가치의 합이 k원이 되도록 하는 경우의 수를 구한다.
입력
- 첫째 줄: 동전 종류 수 n과 목표 금액 k (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000)
- 이후 n줄: 각 동전의 가치
출력
합이 k가 되는 경우의 수를 출력한다.
예제
| 입력 | 출력 |
|---|---|
3 10 1 2 5 | 10 |
풀이
dp[n][k]를 n번째까지의 동전을 사용해서 k원을 만드는 경우의 수로 정의한다. n번 동전 arr[n]을 마지막에 붙여 k - arr[i]원을 만드는 방법의 합산으로 계산한다. 중복 조합을 허용하되 순서가 다른 경우를 같게 취급하기 위해 "작은 번호 동전이 뒤에 오지 않는다"는 규칙을 적용한다.
dp[n][k]를 메모이제이션 방식으로recur(N, K)부터 하향식으로 계산한다.recur(0, k)는 동전 없이 k를 만들 수 없으므로 0을 반환한다.recur(n, 0)은 합산 목표가 0이므로 아무 동전도 쓰지 않는 방법 1가지로 반환한다.dp[n][k]가 null이면 i를 0부터 n까지 순회하며arr[i]를 마지막에 붙여recur(i, k - arr[i])의 합을 구한다.- 최종
dp[N][K]를 출력한다.
핵심 아이디어: dp[n][k]는 n번 이하 동전으로 k를 만드는 방법이다. 마지막에 붙이는 동전 arr[i]를 기준으로 순서 없는 조합을 카운트한다. i번 동전을 마지막에 붙일 때 나머지 k - arr[i]는 i번 이하 동전으로만 구성해야 하므로 recur(i, k - arr[i])를 호출한다. 이 방식으로 {1,2} 와 {2,1}같은 중복 조합을 자동으로 방지한다.
코드
package com.ssafy.an.day099;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Day98BOJ2293동전1DP수정 { // 2293 동전1 DP 2차원으로
static int N, K;
static int[] arr;
static Integer[][] dp;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] str = br.readLine().split(" ");
N = Integer.parseInt(str[0]);
K = Integer.parseInt(str[1]);
arr = new int[N + 1];
for (int i = 1; i < N + 1; i++)
arr[i] = Integer.parseInt(br.readLine());
dp = new Integer[N + 1][K + 1];
System.out.println(recur(N, K));
// for (int i = 0; i < N + 1; i++)
// System.out.println(i + " :: " + Arrays.toString(dp[i]).replaceAll("[\\[\\],ull]", ""));
br.close();
}
private static int recur(int n, int k) {
if (n == 0)
return dp[n][k] = 0;
if (k == 0)
return dp[n][k] = 1;
if (dp[n][k] == null) {
dp[n][k] = 0;
for (int i = 0; i < n + 1; i++)
if (k - arr[i] >= 0)
dp[n][k] += recur(i, k - arr[i]);
}
return dp[n][k];
}
}
// 0 1 2 3 4 5 6 7 8 9 10
// 1 1 1 1 1 1 1 1 1(1)1
// 1 1 2 2 3 3 4 4(5)5 6
// 1 1 2 2 3(4)5 6 7 8 10 << dp[3][10] = dp[1][9] + dp[2][8] + dp[3][5]
// 기억 났다.. 동전을 만드는 경우의 수가 아니라
// 맨 뒤에 동전을 붙혀 나머지를 채우는 경우의 수임..
// 단, 내가 맨 뒤에 붙을 때 나보다 큰 수 뒤에는 못붙음.(작은 동전부터 사용하여 중복회피, 정렬되었다고 생각) ★★★복잡도
- 시간: O(N^2 * K) — 각 dp[n][k]에서 n가지 동전을 탐색
- 공간: O(N * K) — 2차원 dp 배열