[백준 2294번 '동전 2']
https://www.acmicpc.net/problem/2294
[접근 방식]
'동전 1' 문제와 달라진 점은 'k원을 구성하는 경우의 수' -> 'k원을 구성하는 최소 동전 개수' 를 구하는 것이다.
따라서 DP 배열의 구성의의는 "i원을 구성하는 최소동전의 개수" 이여야 한다.
동전에 따라 dp[i] = dp[i] 와 dp[i - coin] + 1 의 최솟값으로 구성한다.
[Java 코드]
/**
* BOJ_2294 동전 2
* https://www.acmicpc.net/problem/2294
* keyword -
*/
import java.io.*;
import java.util.*;
public class Main {
static int n, k;
static int[] coins;
static int[] dp;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
k = Integer.parseInt(st.nextToken());
int INF = k + 1; //최악의 경우 +1
coins = new int[n];
dp = new int[k + 1]; // i원을 만드는데 필요한 동전의 최소 개수
Arrays.fill(dp, INF);
dp[0] = 0;
for (int i = 0; i < n; i++) {
coins[i] = Integer.parseInt(br.readLine());
}
for (int coin : coins) {
for (int i = coin; i <= k; i++) {
dp[i] = Math.min(dp[i], dp[i - coin] + 1);
}
}
System.out.println(dp[k] == k + 1 ? -1 : dp[k]);
}
}
[Rewind]
1. 어려웠던 점
- 아는 문제인데 문제에서 원하는 바를 조금 비트니 접근 자체가 어려웠다.
- dp 배열은 문제에서 원하는 바를 의의로 구성한다.
2. 알게된 점
- DP 배열이 정확이 어떤 의미를 가지고 구성되었는지 명확하게 인지해야 함.
- 점화식을 구성하는데 문제에 대한 명확한 이해가 굉장히 큰 도움이 된다.
3. 개선방안
- '알게된 점' 을 기억해서 문제를 해결해야 한다.
