[Baekjoon] 동전 2

👀 문제 설명

문제

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

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

 

입력

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

 

출력

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

 

예제 입력 1

3 15

1

5

12

 

예제 출력 1

3

 

✍🏻풀이

DP를 사용해 풀었다.

 

예제를 보면, 1원, 5원, 12원 세 가지 동전을 사용해 15원을 만들 수 있는 경우의 수 중, 가장 적은 동전의 개수를 구하면 된다.

DP 테이블을 사용해서 값을 저장해두고, 예전에 구해둔 값으로 현재 값을 구할 수 있다.

1원, 5원, 12원 동전이 있는 것이므로, dp[1] = 1, dp[5] = 1, dp[12] = 1 로 세팅해주고, 나머지 dp 값들은 Integer.MAX_VALUE로 초기화한다.

-> 1원을 만들 수 있는 경우의 수 중, 가장 적은 동전의 개수는 1원 1개

-> 5원을 만들 수 있는 경우의 수 중, 가장 적은 동전의 개수는 5원 1개

-> 12원을 만들 수 있는 경우의 수 중, 가장 적은 동전의 개수는 12원 1개

 

1부터 k까지 dp 테이블을 채워주면 된다.

예를 들어 2원을 만들 수 있는 경우의 수를 구해야 할 때, 내가 가진 동전은 1원, 5원, 12원이므로, 1원 2개를 가지고 만드는 수밖에 없으므로 dp[2] = 2 인데, 이것은 dp[2] = dp[1] + dp[1]과 같다.

마찬가지로 3원을 만들 수 있는 경우의 수를 구해야 할 때, 사용할 수 있는 동전은 1원 3개이므로, dp[3] = 3이고, 이것은 dp[3] = dp[1] + dp[2]와 같다.

그럼 8원을 만들 수 있는 경우의 수를 생각해보면,

1원과 5원을 사용해서 만들 수 있으므로

dp[8]은 dp[1] + dp[7] 또는 dp[5] + dp[3]이 될 수 있으므로, 둘 중 더 작은 값을 dp[8]에 저장하면 되는 것이다.

이렇게 dp 테이블을 채워주고, 최종적으로 dp[k] 값을 출력하면 된다.

 

코드

package boj;

// 동전 2 (https://www.acmicpc.net/problem/2294 )

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

public class BOJ_2294 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		// input
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int n = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());
		int[] coins = new int[n];
		
		for (int i = 0; i < n; i++) {
			coins[i] = Integer.parseInt(br.readLine());
		}
		
		// solve
		int[] dp = new int[k + 1]; // 몇 개의 동전으로 i원을 만들 수 있는지 저장하는 배열(dp[i])
		Arrays.fill(dp, Integer.MAX_VALUE);
		for (int i = 0; i < n; i++) {
			if (coins[i] <= k) // 동전의 가치가 k보다 작은 경우에만 dp에 입력 (이걸 안하면 ArraysOutOfBoundsException 날 수 있다.)
				dp[coins[i]] = 1; // 동전이 3원이라면, dp[3] = 1
		}

		for (int i = 1; i <= k; i++) {
			for (int c = 0; c < n; c++) {
				if (i == coins[c]) continue; // i값이 동전 하나의 가치와 같으면 dp값에 새로 값을 넣어줄 필요가 없다. (1이니까)
				if (coins[c] < i) {
					if (dp[i - coins[c]] != Integer.MAX_VALUE) // dp[i - coins[c]]가 불가능한 경우일 수 있으니까, dp[i - coins[c]]가 가능한 경우에만 비교
						dp[i] = Math.min(dp[i], dp[coins[c]] + dp[i - coins[c]]); // dp[i]값과 dp[coins[c]] + dp[i - coins[c]]를 비교한 후, 더 작은 값을 dp[i]에 넣는다.
				}
			}
		}
		
		bw.write((dp[k] == Integer.MAX_VALUE ? -1 : dp[k]) + "");
		
		bw.flush();
		bw.close();
	}

}