[백준] 12865번: 평범한 배낭 - kotlin

문제

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

풀이

• 메모이제이션
• dp[i][j] 는 i 번째 물건을 기준으로 j 무게를 채울 때 최대 가치를 의미한다.
• dp[i][j] 값을 계산하기 위해서 j 무게가 i 번째 물건의 무게보다 작아 물건을 넣지 못할 때에는 i-1 번째 j 무게의 최대값을 넣어준다.
• 물건을 넣을 수 있는 무게라면, j 무게에서 i 번째 물건의 무게를 뺀 값의 dp 값 + i 번째 가치를 더한 값과 i-1 번째 j 무게의 dp 값을 비교하여 더 큰 값을 넣어준다.

import kotlin.math.max

data class Product(val weight: Int, val value: Int)

fun main() {
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()
    val (N, K) = br.readLine().toString().split(" ").map { it.toInt() }
    val products = mutableListOf<Product>()
    repeat(N) {
        val (W, V) = br.readLine().toString().split(" ").map { it.toInt() }
        products.add(Product(W, V))
    }
    val dp = Array(N) { Array(K + 1) { 0 } }
    for (w in 0..K) {
        if (products[0].weight <= w) {
            dp[0][w] = products[0].value
        }
    }
    for (i in 1 until N) {
        for (w in 0..K) {
            if (products[i].weight <= w) {
                dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - products[i].weight] + products[i].value)
            } else {
                dp[i][w] = dp[i - 1][w]
            }
        }
    }
    bw.write("${dp[N - 1][K]}")
    bw.close()
    br.close()
}

더 좋은 풀이 있으면 댓글 달아주세요!!!