문제 링크

성능 요약

메모리: 14600 KB, 시간: 128 ms

분류

다이나믹 프로그래밍

제출 일자

2025년 1월 28일 03:41:33

문제 설명

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

입력

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

출력

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

풀이

느낀점

• 이전에 풀었던 동전과 다른점은 같은 동전을 여러번 사용할 수 있다는 점이다.
• 최솟값 갱신 조건에서 실수를 했지만, dp는 디버깅이 비교적 쉬운 것 같다.

설계 : 10분

• 동전을 중복되지 않게 입력한 후, 오름차순으로 정렬한다.
• 1차원 dp테이블을 -1로 초기화 한다.(나는 출력시에 쉽게 하려고 했지만, 최솟값 갱신에 혼선이 있을 수 있으므로 각자 편한 방법을 택하면 됨)
• 모든 코인을 순회하며 코인의 가치부터 k까지 값을 갱신한다.
  • 코인 가치의 배수는 i/coin 으로 저장(동전을 오름차순으로 순회하기 때문에 가능)
  • 나머지는 dp[i-coin]이 -1이 아니면 해당 값에 +1해서 저장한다. (이때, 이전 dp[i]와 비교하여 최소값으로 갱신해야 하는데 -1인 경우도 있으니, 경우를 잘 분기한다.)

코드(Java)

• 구현 시간: 20분

/**
 * Author: yngbao97, Yuk Yejin
 * Problem: 동전 2_2294
 * Date: 2025.01.28
 */

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

public class Main {
	static BufferedReader br;
	static BufferedWriter bw;
	static StringTokenizer st;

	public static void main(String[] args) throws Exception {

		br = new BufferedReader(new InputStreamReader(System.in));
		bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		String[] input = br.readLine().split(" ");
        int n = Integer.parseInt(input[0]);
        int k = Integer.parseInt(input[1]);

        Set<Integer> nums = new HashSet<>();
        for (int i = 0; i < n; i++) nums.add(Integer.parseInt(br.readLine()));
        List<Integer> coins = new ArrayList<>(nums);
        Collections.sort(coins);

        int[] dp = new int[k+1];
        Arrays.fill(dp, -1);
        for (int coin : coins) {
            for (int i = coin; i <= k; i++) {
                if (i % coin == 0) dp[i] = i / coin;
                else if (dp[i-coin] > 0) {
                    if (dp[i] > 0) dp[i] = Math.min(dp[i], dp[i-coin] + 1);
                    else dp[i] = dp[i-coin] + 1;
                }
            }
//            System.out.println(Arrays.toString(dp));
        }

        bw.write(String.valueOf(dp[k]));
		bw.flush();
		bw.close();
		br.close();
	}
}