BOJ 2294 - 동전2

woo·2025년 4월 11일

DP도장

목록 보기

6/10

[Gold V] 동전 2 - 2294

문제 링크

성능 요약

메모리: 14308 KB, 시간: 116 ms

분류

다이나믹 프로그래밍

제출 일자

2025년 4월 11일 11:35:14

문제 설명

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

입력

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

출력

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

풀이 설계하기

동전별로 금액을 합쳐서 k원이 되는 방법 중, 동전이 최소인 값을 구해야 한다.
그리고 K원을 만들 수 없다면, -1을 출력한다.

이를 위해서 1원부터 k원까지 필요한 동전의 개수를 저장하는 것부터 시작했다.
그러면 이 저장된 값을 어떻게 활용할 수 있을까?
예를 들어서 이 문제는 동전 금액이 1, 5, 12원이다.
그러면 5원 이전까지는 1, 2, 3, 4원이고 5원은 1원 동전 5개로 만들 수도 있으나 5원 하나로도 가능하다.
마찬가지 원리로 10원은 1원 10개, 5원 1개와 1원 5개, 5원 2개로 가능하고
12원은 1원 12개, 5원 1개 1원 7개, 5원 2개와 1원 2개, 12원 1개로 가능하다.
15원은 1원 15개, ..., 12원 1개와 1원 3개, 5원 3개로 가능하다.

따라서 예제 정답은 3이다.
무언가 규칙이 보이기 시작한다.

점화식 설계하기

5원으로 돌아가 보자.
1원짜리 동전으로만 따질 때에는 4원일 때 1원짜리 동전 하나를 더 추가하여 5개의 동전을 소모한다.
반면, 5원짜리 동전은 시작부터 5원부터 시작하고 동전 하나면 된다.
그리고 5원을 동전 하나로 만들었으면 (5원짜리) 6원은 동전 둘, 7원은 셋.. 으로 나타낸다.
6원은 5원 + 1원, 7원은 5원 + 2원으로 나타낼 수 있다.

즉, 현재 금액의 동전 최소개수 = 현재 금액 - 현재 동전액수 + 1(지금 동전 하나 더 얹음)으로 표현할 수 있다.
이를 식으로 나타내면

dp[i] = Math.min(dp[i], dp[i - coinPrice] + 1)

로 나타낼 수 있다.

시간 복잡도

n이 100이고, k는 10,000이다.
동전마다 (k - 동전 금액)만큼 루프가 발생하므로 시간 복잡도는 O(nk)로 나타낼 수 있다.
백만이면 시간 제한 내 해결이 가능하다.

정답 코드

import java.io.*;
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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        int[] coins = new int[n];
        int[] dp = new int[k + 1];
        Arrays.fill(dp, k + 1);
        dp[0] = 0;

        for (int i = 0; i < n; i++) {
            coins[i] = Integer.parseInt(br.readLine());
        }

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

        System.out.println(dp[k] == k+1 ? -1 : dp[k]);
    }
}

점화식 도출 위한 개념 자체는 단순하나, 실제로 구현 과정에서 너무 복잡하게 생각하여 스스로 꼰 느낌이 있다.
그래서 아이디어 도출은 쉬우나 구체화가 어려운 문제였던 것 같다

부록 - 오답 코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        int[] coins = new int[n];
        int[] dp = new int[k + 1];
        Arrays.fill(dp, k + 1);
        dp[0] = 0;

        for (int i = 0; i < n; i++) {
            coins[i] = Integer.parseInt(br.readLine());
        }

        Arrays.sort(coins);

        for (int i = n - 1; i >= 0; i--) {
            int price = coins[i];
            int maxAmount = k / price;

            for (int j = 1; j <= maxAmount; j++) {
                dp[j * price] = Math.min(dp[j * price], dp[(j - 1) * price] + 1);
            }
        }

        System.out.println(dp[k] == k+1 ? -1 : dp[k]);
    }
}