백준 2294 - 동전 2

문제

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

풀이

문제에서 요구하는 가장 적은 개수의 동전으로 금액을 맞추는 문제를 더 작은 문제로
나누어 생각해보면 다음과 같다.

• 금액 $v$가 주어진 동전 가치에 포함될 경우, 최소의 동전 개수는 1개
• 금액 $k$가 주어진 동전 가치에 포함되지 않을 경우, 최소의 동전 개수는 $k$에서 주어진 동전 가치 $coin_i$를 뺐을 때 해당 값이 주어진 동전으로 구성할 수 있는 경우 중에서 최소 개수 + 1

위 전제에 따라 점화식을 아래와 같이 세울 수 있다.

로직은 다음과 같이 전개된다.

1. 중복된 동전 가치가 입력으로 들어올 수 있으므로 가치는 HashSet에 저장한다.
2. k+1길이의 dp배열을 정의하고, 최소 개수를 저장하기 위해 초기값을 Integer.MAX_VALUE로 초기화한다.
3. dp배열을 순회한다. 인덱스가 충족하고자 하는 금액이다. 해당 금액이 주어진 동전 가치에 존재할 경우, 최소 개수 1로 dp[i]를 설정한다. 그 외에 경우 점화식에 따라 dp[i-coin]+1 중 가장 작은 값으로 설정한다.
4. 동전 가치보다 충족하고자 하는 금액이 작을 경우, 특정 금액이 동전으로 구성될 수 없는 경우는 별도의 분기문을 통해 제외한다.
5. 모든 금액 경우를 구성한 이후, dp[k]가 초기값이라면 동전으로 구성될 수 없는 경우이므로 -1을 출력. 이외의 경우 dp[k]의 값을 출력한다.

로직의 시간복잡도는 $k$개의 금액에 대해 $n$개의 동전으로 구성되는 경우를 고려하므로, $O(kn)$으로 수렴한다. $n=100$,$k=10,000$인 최악의 경우에도 무난히 제한 조건
1초를 통과한다.

코드

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

import static java.lang.Integer.MAX_VALUE;
import static java.lang.Integer.parseInt;

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 = parseInt(st.nextToken());
        int k = parseInt(st.nextToken());

        HashSet<Integer> coins = new HashSet<>();
        while (n-- > 0) {
            coins.add(parseInt(br.readLine()));
        }

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

        for (int i = 1; i <= k; i++) {
            if (coins.contains(i)) {
                dp[i] = 1;
                continue;
            }

            for (Integer coin : coins) {
                if (i - coin <= 0 || dp[i - coin] == MAX_VALUE) continue;

                dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
        }

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

결과