백준 2294 동전 2 Kotlin (dp)

문제 출처 : https://www.acmicpc.net/problem/2294

2294번: 동전 2

문제

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

사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.

입력

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

출력

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

알고리즘 분류

• 다이나믹 프로그래밍

풀이

2022.08.01 - [알고리즘 문제 풀이/백준] - 백준 2293 동전 1 Kotlin (dp)

이전 동전 1 문제와 비슷하다.

이번엔 k원을 만드는 경우의 수를 구하는 것이 아닌, k원을 최소 개수의 동전으로 만들 때 그 최소 개수를 구하는 것이다.

dp[i] = i원을 만드는 데에 드는 최소 동전 개수

dp에 최솟값들로 갱신해주기 위해 초기값으로 INF값을 넣어놓는다.

이번에도 의미 없는 값인 dp[0]에 점화식을 적용하기 위해 0이란 값을 넣어놓는다.

점화식은 어떻게 짜면 좋을까?

이전과 동일하게 2원짜리 동전으로 i원을 만들려면 i-2원에 2원을 더해야 한다.

따라서 i-2원을 만드는 데에 필요한 동전의 최소 개수를 알고 있다면 여기에 동전 2원짜리 하나 추가하면 그것이 i원을 만드는 동전의 최소 개수이다.

dp에는 어떠한 경우에도 최소 동전 개수가 들어온다는 것이 보장되어야 한다.

예제에서 1,5,12라는 동전이 주어졌다.

14 + 1

10 + 5

3 + 12

이므로, 14일 때, 10일 때, 3일 때 필요한 최소 개수들 중 가장 작은 값을 저장해야 한다.

따라서 점화식은 dp[i] = min(dp[i], dp[i-coin]+1)로 세울 수 있다.

k원을 만들 수 없는 경우 -1을 출력해야 하는 것을 주의하자.

코드

val br = System.`in`.bufferedReader()
fun getIntList() = br.readLine().split(' ').map { it.toInt() }
fun getInt() = br.readLine().toInt()

fun main() = with(System.out.bufferedWriter()) {
    val (n,k) = getIntList()
    val dp = IntArray(k+1){Int.MAX_VALUE}
    dp[0] = 0
    repeat(n){
        val coin = getInt()
        for(i in coin .. k){
            if(dp[i-coin]!=Int.MAX_VALUE) {
                dp[i] = dp[i].coerceAtMost(dp[i-coin]+1)
            }
        }
    }
    if(dp[k]==Int.MAX_VALUE){
        write("-1")
    }
    else {
        write("${dp[k]}")
    }
    close()
}