[Java Algorithm] 동전2 BOJ #2294

문제

https://www.acmicpc.net/problem/2294

2294번: 동전 2

 

내 문제 풀이

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

public class BOJ_2294 {

	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		st = new StringTokenizer(in.readLine());
		int n = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());
		int[] coin = new int[n];
		for(int i = 0; i < n; i++) {
			coin[i] = Integer.parseInt(in.readLine());
		}

		int[] memory = new int[k+1];
		Arrays.fill(memory, 100001);
		memory[0] = 0;
		for(int c: coin) {
			for(int i = c; i < k+1; i++) {
				memory[i] = Math.min(memory[i], memory[i - c] + 1);
			}
		}

		System.out.println(memory[k] == 100001 ? -1 : memory[k]);
	}
}

👉 DP 문제

점화식 : memory[i] = Math.min(memory[i], memory[i - c] + 1);

 

✔️ 반례 추천

2 100
7
8

 

💡 피드백

• DP는 항상 점화식 구하는게 힘든데..!! 이번에도 처음에 헛다리 짚어서 엄청 오래걸렸다.ㅎ