[백준/JAVA] 2294_동전2

백준🔗

2294번: 동전 2

 

 

문제

 

 

간단 풀이

간단한 1차원 dp 문제이다.

dp[i] : i원을 만들 때 사용하는 동전의 개수

위와 같이 정의하고, 주어진 n가지 동전 각각을 쓰거나 or 쓰지 않거나의 경우를 모두 비교해서 최소 개수로 k원을 만드는 경우를 찾는다.

 

한 가지 주의해야 할 점은, 처음에 dp배열을 Integer.MAX_VALUE로 초기화 했는데, 

계산 과정에서 dp[i - coin[j]] + 1 이렇게 1을 더하게 되기 때문에 Integer.MAX_VALUE로 초기화를 하면 int형의 범위를 벗어나면서 오버플로우가 발생한다. 따라서 Integer.MAX_VALUE-1 혹은 적절한 최대값으로 초기화를 해주어야 했다.

 

 

 

코드

import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) throws Exception {
		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[] coin = new int[n];
		for (int i = 0; i < n; i++) {
			coin[i] = Integer.parseInt(br.readLine());
		}
		int[] dp = new int[k + 1];
		Arrays.fill(dp, k + 1);
		dp[0] = 0;
		for (int i = 1; i <= k; i++) {
			for (int j = 0; j < n; j++) {
				if (i >= coin[j]) {
					dp[i] = Math.min(dp[i], dp[i - coin[j]] + 1);
				}
			}
		}
		if (dp[k] == k + 1) {
			System.out.println(-1);
		} else {
			System.out.println(dp[k]);
		}
	}
}

 

 

참고 자료