[백준 2294번] [Kotlin] 동전 2

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

2294번: 동전 2

 

난이도 : 골드 5
태그 : 다이나믹 프로그래밍

 

 

설명

동전의 개수를 최소로 하는 문제입니다.

같은 단위의 동전이 여러개 주어질 수 있으므로 중복제거를 해야 합니다.

 

dp의 각 원소는 각 동전을 만들기 위한 최소의 동전 개수입니다.

0원을 만들기 위한 동전의 개수는 0개이므로, dp[0] = 0으로 초기화합니다.

1, 5, 12원 동전을 사용해 15원을 만들어야 합니다.

 

1원을 만들기 위해선 1원짜리 동전 1개가,

5원을 만들기 위해선 1원짜리 5개 혹은 5원짜리 1개가 필요합니다.

10원은 5원짜리 2개 혹은 5원 1개 + 1원 5개, 1원 10개가 필요합니다.

10원의 경우, 1원짜리 동전은 (10-1 = 9)원을 만들기 위해서는 9원을 만들기 위한 최소한의 동전개수,

즉 dp[10]은 dp[10]과 dp[10 - 1] + 1 중 작은 값이 됩니다.

하지만 10원은 5원짜리 두개를 통해서도 만들 수 있습니다.

즉, dp[10] = min(dp[10], dp[10-5] + 1) 입니다.

 

12원의 경우,

1원짜리 동전은 dp[11] + 1,

5원짜리는 dp[7] + 1,

12원짜리 동전은 dp[0] + 1으로, 셋 중 가장 작은 값이 됩니다.

 

 

소스코드

import java.io.BufferedReader
import java.io.InputStreamReader
import kotlin.math.min


fun main(): Unit = with(BufferedReader(InputStreamReader(System.`in`))) {
    val MAX = 1000000
    val (n, k) = readLine().split(" ").map { it.toInt() }

    val coins = Array(n) { 0 }
    repeat(n) {
        coins[it] = readLine().toInt()
    }

    val dp = Array(k + 1) { MAX }
    dp[0] = 0

    for (i in 1..k) {
        for (coin in coins) {
            if (i - coin >= 0) {
                dp[i] = min(dp[i], dp[i - coin] + 1)
            }
        }
    }
    println(if (dp[k] == MAX) -1 else dp[k])
}

 

이를 코드로 나타내면 위와 같습니다.

돈을 만들 수 없을 때는 -1을 출력해야 합니다.

 

 

후기

다이나믹 프로그래밍.

사실 그닥 다이나믹 하지도 않고 프로그래밍이랑도 큰 관련이 없다고 합니다.

그냥 투자받기 좋을 것 같은 이름으로 지었다네요.