[BOJ] 백준 2294번 동전2 (Java)

#2294 동전2

난이도 : 실버 1

유형 : DP

2294번: 동전 2

▸ 문제

n가지 종류의 동전이 있다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. 각각의 동전은 몇 개라도 사용할 수 있다.

사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.

▸ 입력

첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어질 수도 있다.

▸ 출력

첫째 줄에 사용한 동전의 최소 개수를 출력한다. 불가능한 경우에는 -1을 출력한다.

 

문제 풀이  

동전1 문제의 상향 버전이다. 주어진 동전의 종류로 k원을 만들 수 있는 동전의 최소 개수를 구하는 문제이다. Bottom-up방식으로 주어진 n개의 동전을 차례대로 탐색하여 만들 수 있는 개수의 최솟값을 구하는 식으로 접근하였다.

 

구상

dp는 2차원 배열로, 주어진 동전(coin[i])의 금액과 j원을 만들 수 있는 동전의 개수를 저장한다.

• dp[i][j] = coin[0~i]들로 j원을 만들 수 있는 동전의 최소 개수
  • 동전 가치의 최대는 100,000이므로 최솟값 비교를 위해 dp배열을 100,001로 초기화해준다

 

시뮬레이션

1. 주어진 코인 n개를 순차적으로 탐색해준다. i : 0~n-1 
2. 현재의 동전(coin[i])가 j보다 작거나 같으면 해당 동전으로 j원을 만들 수 있는 최소의 동전 개수를 구해준다. j : 1~k 

idx	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
coin[0]=1	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
coin[1]=5	0	1	2	3	4	1	2	3	4	5	2	3	4	5	6	3
coin[2]=12	0	1	2	3	4	1	2	3	4	5	2	3	1	2	3	3

 

해당 2차원 배열 dp 탐색과정을 코드로 표현하면 다음과 같다.

for(int i=0; i<n; i++) {
	int now = coin[i];
	for(int j=1; j<k+1; j++) {
		if(i==0) {
			if(j>=now) dp[i][j] = Math.min(dp[i][j-now]+1, dp[i][j]);
		}else {
			if(j>=now) {
				dp[i][j] = Math.min(dp[i][j-now]+1,dp[i-1][j]);
			}else {
				dp[i][j] = dp[i-1][j];
			}
		}
	}
}

 

최적화

위의 시뮬레이션을 보면 알겠지만 사실상 dp의 값이 변경되는 부분은 j= coin[i]일 때 부터이다. 필요없는 연산과정을 제거하고 이를 단축시키면 dp배열과 코드를 다음과 같이 줄일 수 있다.

 

dp는 1차원 배열로 주어진 동전(coin[i])의 금액과 j원을 만들 수 있는 동전의 개수를 저장한다.

• dp[i] = coin[0~i]들로 j원을 만들 수 있는 동전의 최소 개수

for(int i=0; i<n; i++) {
	for(int j= coin[i]; j< k+1; j++) {
		dp[j] = Math.min(dp[j], dp[j - coin[i]] +1);
	}
}

 

풀이 코드 

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

public class Main {
	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[] 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, 100001);
		dp[0] = 0;
		for(int i=0; i<n; i++) {
			for(int j= coin[i]; j< k+1; j++) {
				dp[j] = Math.min(dp[j], dp[j - coin[i]] +1);
			}
		}
		System.out.println(dp[k] == 100_001? -1 : dp[k]);
	}
}