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

문제

 

11052번: 카드 구매하기

 

---

풀이

 

 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]$

 

 이중 반복문에서 점화식을 활용하여 최대 비용을 찾으면 된다.

 

---

코드

 

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) {
        for(j in 1 .. i) {
            dp[i] = maxOf(dp[i], dp[i - j] + price[j-1])
        }
    }

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