Q2294. 동전 2

특정 value의 최소값을 구하며 나아가는 로직

import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Q2294 { static int[] dp, coin; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int coinNum = Integer.parseInt(st.nextToken()); coin = new int[coinNum+1]; int value = Integer.parseInt(st.nextToken()); dp = new int[value+1]; for (int i = 1; i <= coinNum; i++) { st = new StringTokenizer(br.readLine()); int nowCoin = Integer.parseInt(st.nextToken()); for (int j = nowCoin; j <= value; j++) { int index = j - nowCoin; if (index == 0) { dp[j] = 1; } else if (dp[index] > 0) { if (dp[j] == 0) { dp[j] = dp[index]+1; } else { dp[j] = Math.min(dp[j], dp[index]+1); } } } } if (dp[value] == 0) { dp[value] = -1; } System.out.println(dp[value]); } }