[백준] 2294 - 동전2 (Java/자바)

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

2294번: 동전 2

동전의 값어치를 읽어올때마다 해당 동전을 하나 사용(+1)하면서 남은 금액을 만드는 동전의 최소 개수(+dp[j-money])의 합이 더 작다면 dp를 갱신해준다.

사실 예제 테스트케이스에서 동전의 값어치가 작은 순서대로 주어져서 값을 배열에 저장하지 않았는데 랜덤으로 나온다면 sort하는게 더 빠를 것 같다.

package DP;

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

public class Main_BOJ_2294_동전2_S1_이선민_100ms {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int n = Integer.parseInt(st.nextToken()); // 동전의 종류
		int k = Integer.parseInt(st.nextToken()); // 만들려는 금액
		int[] dp = new int[k + 1]; // 현재 금액을 만드는데 사용한 동전의 최소 개수
		Arrays.fill(dp, 10001); // 동전의 최소가치가 1이고 k가 10000일 경우가 최대이므로
		dp[0] = 0;
		for (int i = 0; i < n; i++) {
			int money = Integer.parseInt(br.readLine()); // 동전 금액
			for (int j = money; j < dp.length; j++) {
				if (dp[j] > dp[j - money] + 1) {
					dp[j] = dp[j - money] + 1;
				}
			}
		}

		if (dp[k] == 10001) { // 원하는 금액을 만들 수 없는 경우
			System.out.print(-1);
		} else {
			System.out.print(dp[k]);
		}
	} // end of main

} // end of class