[BaekJoon] 2294 동전 2

1.  문제 링크

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

2.  문제

요약

• n가지 종류의 동전들은 몇 개라도 사용할 수 있고, 이 동전들을 적당히 사용하여 가치의 합이 k원이 되도록 하려고 합니다.
• 이 때, 동전의 개수를 최소로 사용하여 k원을 만드려고 합니다.
• 사용한 동전의 구성이 같은데 순서만 다른 것은 같은 경우입니다.
• n가지 종류의 동전이 주어질 때, k원을 만들 때의 사용한 동전의 최소 개수를 구하는 문제입니다.
• 입력: 첫 번째 줄에 1보다 크거나 같고 100보다 작거나 같은 동전 종류의 개수 n과 1보다 크거나 같고 10,000보다 작거나 같은 k가 주어지며 두 번째 줄부터 100,000보다 작거나 같은 자연수인 n개의 줄에는 각 동전의 가치가 주어집니다.
  • 가치가 같은 동전이 여러 번 주어질 수도 있습니다.
• 출력: 첫 번째 줄에 사용한 동전의 최소 개수를 출력합니다. 불가능할 때는 -1을 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
	public int getMinCoinNum(int n, int k, int[] coins) {
		int[] dp = new int[k + 1];
		for(int i = 1; i <= k; i++) {
			dp[i] = Integer.MAX_VALUE - 1;
		}
		for(int i = 1; i <= n; i++) {
			for(int j = coins[i]; j <= k; j++) {
				dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);
			}
		}
		if(dp[k] == Integer.MAX_VALUE - 1) {
			return -1;
		}
		return dp[k];
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		String[] input = br.readLine().split(" ");
		int n = Integer.parseInt(input[0]);
		int k = Integer.parseInt(input[1]);
		int[] coins = new int[n + 1];
		for(int i = 1; i <= n; i++) {
			coins[i] = Integer.parseInt(br.readLine());
		}
		br.close();
		Main m = new Main();
		bw.write(m.getMinCoinNum(n, k, coins) + "\n");
		bw.flush();
		bw.close();
	}
}

4.  접근

• 해당 문제는 DP를 이용하여 구할 수 있는 문제입니다.
• 1원부터 k원까지 각 금액에서 필요한 최소 동전 수를 나타내는 배열 dp를 생성합니다.
• 주어진 동전 가치들에 대해 1원부터 k원까지 각 금액을 만들 때 필요한 동전 개수들을 계산합니다.
• 동전 가치들을 하나씩 지날 때마다 이전까지의 동전 가치들에서 구한 각 금액에서의 동전 개수를 이용하여 현재 동전 가치에서의 각 금액에 대한 동전 개수를 구합니다.
• 현재 가치의 동전을 하나 사용하고 남은 금액에 대하여 이전까지 구한 해당 금액에서의 최소 동전 개수를 이용하면 현재 가치의 동전을 이용한 최소 동전 개수가 됩니다.
• 이렇게 구한 동전 개수와 이전까지 구한 현재 금액에서의 최소 동전 개수를 비교하여 더 적게 사용한 것이 현재 금액에서의 최소 동전 개수가 됩니다.
• 현재 동전의 가치가 coins[i]일 때, m원에서의 최소 동전 개수를 구하는 점화식은 아래와 같이 구해질 수 있습니다.
  • dp[m] = Math.min(dp[m], dp[m - coins[i]] + 1);
• 위에서 구한 점화식을 이용하여 k원을 만드는 최소 동전 개수를 구합니다.

1. 주어진 동전 가치들을 coins 배열에 넣어주고 각 금액에서의 최소 동전 개수를 나타내는 dp 배열을 생성합니다. dp 배열의 값은 (정수의 최소값 - 1)로 초기화합니다.
2. 첫 번째 동전 가치부터 시작하여 마지막 동전 가치까지 반복문을 돌면서 각 금액에서의 최소 동전 개수를 구합니다.
   • 현재 동전 가치부터 k원까지 반복문을 돌면서 위에서 구한 점화식을 이용하여 각 금액에서의 최소 동전 개수를 구합니다.
3. 2번의 반복문이 끝난 후에 dp[k] 값이 dp를 초기화해준 값과 같다면 주어진 동전 가치들을 이용하여 k원을 만들 수 없다는 뜻이기 때문에 -1을 출력합니다.
4. 그렇지 않다면 dp[k] 값이 k원에서의 최소 동전 개수이기 때문에 이를 출력합니다.