[백준] 평범한 배낭 - 골드 5 (Kotlin)

문제

이 문제는 아주 평범한 배낭에 관한 문제이다.

한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다.

준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자.

입력

첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다.

입력으로 주어지는 모든 수는 정수이다.

출력

한 줄에 배낭에 넣을 수 있는 물건들의 가치합의 최댓값을 출력한다.

풀이

맨 처음 풀었을 당시엔 DP Table 을 '무게'로 설정했다.
이 방법은 애초에 접근이 틀렸기에 반례도 생각하지 못하고 왜 틀린지도 몰랐다.
그 다음은 DP 에 대해 조금 더 공부하고, DP Table 을 [물건의 갯수][무게] 인 2차원 배열로 설정했다.
이 문제를 정의해보면 P(4, 7) 로 정의할 수 있다.
물건이 총 4개이고, 최대 무게가 7일 때 최대 가치를 구하는 문제이다.
따라서 DP Table 을 물건의 갯수, 무게로 설정했다.
그렇다면 물건의 갯수는 0 ~ N 의 범위를 가지고, 무게는 0 ~ K 까지 이므로
DP = Array(N+1) { IntArray(K+1) } 이 될 것이다.
이제 상향식 DP 를 사용해보도록 하겠다.
문제를 다음 문제로 확장시킬 때, 즉, 물건이 1개인 상황에서 물건이 2개로 늘어날 때 ( DP[1][K] > DP[2][K] ) 두 가지 고려사항이 있다.
물건이 가방안에 포함되는 경우와 포함되지 않는 경우
따라서 물건이 가방안에 넣을 수 있다면 해당 가치만큼 추가가 되고, 가방안에 넣지 않는 경우엔 추가하지 않는다.
그 두 값의 최댓값을 계속 갱신하다보면 마지막 N, K 배열에는 N개의 물건으로 최대 무게가 K일 때의 최대 가치를 구할 수 있다.

소스 코드

import kotlin.math.max

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

fun main(args: Array<String>) {
/*
4 7
6 13
4 8
3 6
5 12
*/
    val (N, K) =  readLine()!!.split(' ').map { it.toInt() }
    val dp = Array(N+1) { IntArray(K+1) {0} }
    val itemList = mutableListOf<Item>()

    repeat(N) {
        val (W, V) = readLine()!!.split(' ').map { it.toInt() }
        itemList.add(Item(W, V))
    }

    for (n in 1..N) {
        val w = itemList[n-1].weight
        val v = itemList[n-1].value
        for (k in 1..K) {
            if (k - w >= 0)
                dp[n][k] = max(dp[n-1][k], dp[n-1][k-w] + v)
            else
                dp[n][k] = dp[n-1][k]
        }
    }

    println(dp[N][K])
}

요약

유명한 문제라고 하는데 처음 풀어보려고 하면 굉장히 어려웠던 것 같다.
말로는 설명하기가 어려워서 유튜브나 구글링을 통해 배낭문제라고 검색한 뒤 표나 그림을 통한 설명을 보는게 이해가 빠를 것 같다.