[2294번] 동전2 ( 그리디로 풀 수 없는 DP 문제, 배열 fill 함수, 동전0의 확장인데 더 쉬운? )

---

동전 2 보다 동전 1이 더 어려운 이유가 무엇이지..?
동전의 경우의 수가 (1,2,5) 라고 가정하고 코드를 구현했다.

---

✅ 그리디와 DP

동전0 을 풀 때 그리디로 풀었는데, 그리디로 풀려면 반례가 없어야 한다고 했다.
-> 동전이 배수, 약수 등의 어느정도 규칙이 있을 때 접근 가능한 알고리즘인 걸 빨리 눈치채고 그리디가 아닌 다른 방식으로 접근해야 함.
-> DP를 사용함 (아이디어 참고)
-> 그러면, 점화식 도출해야 함

---

✅ 점화식 도출

이거 풀기 전에 동전1 부터 풀고와야 할 것 같다.
풀고오겠다.
ㅎ 빈손으로 돌아왔다.
동전 2는 풀이 보니까 바로 이해하겠는데, 동전 1은 규칙찾는 거라서 그런가? 이해하기가 동전 2보다 더 어려운데??? 왜지??

배열은 최대값으로 채워준다.

Arrays.fill(dp, 100001);

---

✅ 점화식 -> 코드

점화식 도출까지 ok.
Math.min 부분을 잘 구현해야 한다.

사전 setting

coin[] : 동전 종류를 담는 배열 (n까지)
dp[] : 동전의 개수가 최소가 되는 경우의 수를 저장하는 배열 (k까지)

점화식을 dp로 표현하는 방법

만약 (1,2,5)가 동전의 경우의 수라면

amount = 3일 때,

1) dp[3] = Math.min(100001, dp[2]+1 = 3) -> 3

2) dp[3] = Math.min( dp[2]+1 = 3, dp[1]+1 = 2) -> 2

3) 동전이 5인 경우는 조건문을 만족시키지 않으므로 계산되지 않는다.

private static void findMinCoins(int amount) {
	for (int c : coin) {
		if (amount >= c) {
					dp[amount] = Math.min(dp[amount], dp[amount - c] + 1);
		}
	}
}

---

✅ 불가능한 경우

아아 테스트 케이스만 맞추면 안된다.
불가능한 경우도 고려해줘야 한다!

틀린 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;


public class Main {
	static int coin[];
	static int dp[];

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());

		coin = new int[n];
		dp = new int[k + 1];

		for (int i = 0; i < n; i++) {
			coin[i] = Integer.parseInt(br.readLine());
		}

		Arrays.fill(dp, 100001);

		dp[0] = 0;
		dp[1] = 1;
		dp[2] = 2;


		for (int i = 3; i < k + 1; i++) {
			findMinCoins(i);
		}

		System.out.println(dp[k]);
	}

	private static void findMinCoins(int amount) {
		for (int c : coin) {
			if (amount >= c) {
				dp[amount] = Math.min(dp[amount], dp[amount - c] + 1);
			}
		}
	}
}

---

✅ 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;


public class Main {
	static int coin[];
	static int dp[];
	static int n = 0, k = 0;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		k = Integer.parseInt(st.nextToken());

		coin = new int[n];
		dp = new int[k + 1];

		for (int i = 0; i < n; i++) {
			coin[i] = Integer.parseInt(br.readLine());
		}

		Arrays.fill(dp, 100001); //최소값 계산 세팅
		dp[0] = 0;

		int result = findMinCoins();
		System.out.println(result);

	}

	private static int findMinCoins() {

		for (int amount = 1; amount < k + 1; amount++) {
			for (int c : coin) {
				if (amount >= c) {
					dp[amount] = Math.min(dp[amount], dp[amount - c] + 1);
				}
			}
		}

		// 100001이 채워져 있으면!
		return dp[k] > k ? -1 : dp[k];

	}

}

---