[백준][Kotlin] 12865 평범한 배낭

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

12865번: 평범한 배낭

풀이

1. 입력에 대해서 가질 수 있는 최대 가치에 대해서 모두 검색 한다.

2. 아래의 표를 이용해서 점화식을 구한다. (가로 : 최대 무게 경우의 수(K), 세로 : 물건 순서(N))

	1	2	3	4	5	6	7
1	0	0	0	0	0	13	13
2	0	0	0	8	8	13	13
3	0	0	6	8	8	13	14
4	0	0	6	8	12	13	14

코드

import java.io.*
import java.util.*

fun main(args: Array<String>) {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val st = StringTokenizer(br.readLine())
    val N = st.nextToken().toInt()
    val K = st.nextToken().toInt()
    val dp = Array(N + 1) {
        IntArray(K + 1)
    }

    val W = IntArray(N + 1)
    val V = IntArray(N + 1)

    repeat(N) {
        StringTokenizer(br.readLine()).apply {
            W[it + 1] = nextToken().toInt()
            V[it + 1] = nextToken().toInt()
        }
    }

    for (i in 1..N) {
        for (j in 1..K) {
            if (W[i] > j) {
                dp[i][j] = dp[i - 1][j]
            } else {
                dp[i][j] = max(dp[i - 1][j], V[i] + dp[i - 1][K - W[i]])
            }
        }
    }

    println(dp[N][K])
}

private fun max(a: Int, b: Int): Int {
    return if (a < b) b else a
}