[ 백준 ] 2294 동전 2

📌 Problem

주어진 N개의 가치를 지닌 동전들이 무한개 있다고 했을 떄 이들을 조합하여 K 가치를 만들 수 있는 최소 동전 개수를 출력하면 된다.

📌 Solution

동적 프로그래밍의 대표적인 문제이다. 가치 V를 동전 C를 하나 더하여 만들 수 있는 동전의 개수는 다음과 같다.

VS[V] = min(VS[V], VS[V - C] + 1)

이 식을 이용해서 매 가치마다 모든 동전에 대한 탐색을 진행한다.

📌 Example

예제 1번에 대한 풀이는 다음과 같다.

C는 가치(column)을 만들 수 있는 동전의 최소 개수이다. 처음에 가치 0을 모두 0으로 한다.
가치 1을 만들 수 있는 경우는 1원 동전을 1개 사용하는 것이다.

가치 4까지는 1원 동전으로만 만들 수 있다.

가치 5부터는 11까지는 5원 동전도 사용이 가능하다.

가치 12부터는 12원 동전도 사용이 가능하다.

최종적으로 15원을 만들 수 있는 동전의 최소 개수는 3개이다.

📌 Code

final int MAX_COIN_NUMBER = 10_001;

StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
int[] coins = new int[Integer.parseInt(tokenizer.nextToken())];
int[] coinNumbers = IntStream.range(0, Integer.parseInt(tokenizer.nextToken()) + 1)
        .map(i -> i > 0 ? MAX_COIN_NUMBER : 0).toArray();
for (int c = 0; c < coins.length; c++) coins[c] = Integer.parseInt(reader.readLine());

for (int value = 1; value < coinNumbers.length; value++)
    for (int coin : coins)
        if (coin <= value)
            coinNumbers[value] = Math.min(coinNumbers[value], coinNumbers[value - coin] + 1);

int coinNumber = coinNumbers[coinNumbers.length - 1];
result.append(coinNumber == MAX_COIN_NUMBER ? -1 : coinNumber);