#2294 : 동전 2

풀이방법

사용된 것:

다이나믹 프로그래밍(DP)

TreeSet

각각의 동전의 가치 값들을 저장하는 데 트리셋을 사용하였다.

중복값을 없애기가 편하고,

집합에 포함된 모든 값을 각각 한 번씩만 이용할 때 pollFirst()가 편해서 사용하였다.

 

 

2022.03.30

다이나믹 프로그래밍 문제이다.

k원의 금액을 만들어야 할 때,

1원의 금액의 경우부터 k원의 금액에 이르기까지

자신보다 적은 금액의 동전 개수를 이용해 자신의 금액을 구해가며

차근차근 최적의 데이터를 알아낼 수 있기 때문이다.

 

크기가 k+1인 정수형 1차원 배열 dp를 만든 다음,

dp[i]에 i원을 만들기 위한 최소의 동전 개수를 저장한다.

그 후 dp[k]의 값을 이용하여 답을 구하면 된다.

 

첫 몇 개의 데이터를 가지고 손으로 직접 구해보면 결과값의 패턴을 알 수 있다.

이 패턴을 알고리즘으로 구체화시키면 dp를 다 채울 수 있다.

아래의 코드를 참고하자.

 

-1을 출력해야 하는 경우를 골라내는 법은 다음과 같다.

배열에 최적의 값들을 넣어주기 전에, 0원(dp[0])을 제외한 모든 금액의 동전 개수(dp의 모든 요소)를 100001로 초기화한다. 0원(dp[0])만 0개로 설정한다.

주어지는 금액(k)의 최대 액수가 100000원인데, 그럼 1원짜리 동전이 존재할 때를 가정해도 최악의 경우 가장 많이 필요한 동전 개수는 100000개이기 때문이다. 이 최악의 경우보다 1 큰 값이 100001을 저장해주는 것이다.

이후 최적의 값을 채워주는 과정에서

dp[i] = Math.min(dp[i]에 원래 있던 값, 새로 계산된 값)

이러한 Math.min()을 사용하기 때문에, 가능한 값이 존재하기만 한다면 모든 과정이 끝난 후에는 무조건 100001보다 작은 수가 저장될 것이다.

최적의 개수를 찾는 과정이 다 끝났는데도 여전히 100001이 저장되어있는 금액은 현재 가지고 있는 동전으로 만들 수 있는 경우의 수가 아예 없는 것이다.

따라서 dp[k]에 100001이 저장되어있다면 화면에 -1을 출력하면 된다.

 

코드

Java(2022.03.30)

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

public class Main {

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		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());
		
		//중복값 제거
		TreeSet<Integer> ts = new TreeSet<Integer>();
		for(int i = 0; i<n; i++) {
			ts.add(Integer.parseInt(br.readLine()));
		}
		
		//dp 배열 생성
		int[] dp = new int[k+1];
		Arrays.fill(dp, 100001);	//최악의 경우의 동전 갯수인 100000보다 1 큰 수로 모두 채워두기
		dp[0] = 0;	//0원을 만들 수 있는 동전 개수는 0개
		//1원의 경우부터 dp배열 채우기
		while(!ts.isEmpty()) {
			int num = ts.pollFirst();
			for(int i = num; i<k+1; i++) dp[i] = Math.min(dp[i], dp[i - num]+1);
		}
		
		if(dp[k] == 100001) System.out.print(-1);
		else System.out.print(dp[k]);
	}

}