[백준] 16194번: 카드 구매하기 2 - Kotlin[코틀린]

문제

 

16194번: 카드 구매하기 2

 

---

풀이

 

 DP(동적 프로그래밍)으로 해결하는 문제이다. 민규가 카드를 N개를 구매하는 방법은 여러가지가 있으며 다음과 같다.

  - 카드 1개가 포함된 카드팩 + 카드 N-1개 구매: price[1] + dp[N-1]
  - 카드 2개가 포함된 카드팩 + 카드 N-2개 구매: price[2] + dp[N-2]
  - 카드 3개가 포함된 카드팩 + 카드 N-3개 구매: price[3] + dp[N-3]
  ...
  - 카드 M개가 포함된 카드팩 + 카드 N-M개 구매(점화식): $dp[N] = price[M] + dp[N−M]$

 먼저 dp 배열을 해당하는 카드팩을 구매하는 방법으로 초기화하고 이중 반복문을 통 점화식을 활용하여 최소 비용을 찾으면 된다.

 

---

코드

 

fun main() {
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()

    val num = br.readLine().toInt()
    val price = br.readLine().split(' ').map { it.toInt() }
    val dp = IntArray(num+1)

    for(i in 1 .. num) {
        dp[i] = price[i-1]
        for(j in 1 .. i) {
            dp[i] = minOf(dp[i], dp[i - j] + price[j-1])
        }
    }

    bw.write("${dp[num]}")
    bw.flush()
    bw.close()
    br.close()
}