백준 12865. 평범한 배낭

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

12865번: 평범한 배낭

 

import kotlin.math.max

val bags = ArrayList<Pair<Int, Int>>()

fun main(args: Array<String>) {
    val (n, k) = readln().split(" ").map { it.toInt() }

    repeat(n) {
        val (w, v) = readln().split(" ").map { it.toInt() }

        bags.add(Pair(w, v))
    }

    val dp = Array(n) { IntArray(k + 1) { -1 } }

    println(getMaxValue(dp, 0, k))
}

fun getMaxValue(dp: Array<IntArray>, x: Int, y: Int): Int {
    if (x == bags.size) {
        return 0
    }

    if (dp[x][y] != -1) {
        return dp[x][y]
    }

    dp[x][y] = getMaxValue(dp, x + 1, y)
    if (y - bags[x].first >= 0) {
        dp[x][y] = max(dp[x][y], getMaxValue(dp, x + 1, y - bags[x].first) + bags[x].second)
    }

    return dp[x][y];
}

 

풀이

물건들이 일렬로 나열되어 있을때, dp[x][y] = x번째 물건, 그 때의 버틸 수 있는 무게 값이 y일 때 가질 수 있는 최대 가치값으로 뒀을 때,

1. 현재 물건을 선택하지 않고 다음 물건으로 이동한 경우

2. 현재 물건을 선택한 경우 (선택 가능한 무게라면)

위 2가지 경우로 나눠서 최대값을 구하면 된다.