#12865 평범한 배낭

 

코딩테스트를 위해 알고리즘을 다시 공부하려고 한다!

기존에 c++로 진행했던걸 kotlin으로 변경해서 다시 풀어보려고 한다

 

문제

---

 

코드

---

import kotlin.math.max

fun main() {
    val (n, k) = readln().split(' ').map { it.toInt() }
    val w = IntArray(n + 1)
    val v = IntArray(n + 1)
    val dp = Array(n + 1) { IntArray(k + 1) }

    for (i in 1..n) {
        val (weight, value) = readln().split(" ").map { it.toInt() }
        w[i] = weight; v[i] = value
    }
    for (i in 1..n) {
        for (j in 1..k) {
            dp[i][j] =
                if (j >= w[i]) max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i])
                else dp[i - 1][j]
        }
    }
    println(dp[n][k])
}

 

 

 

문제 풀이

---

이전에 한 번 풀었었는데, 기억이 잘 나지 않아서 dp 개념을 복습했다

배열은 [물건 개수 + 1][들 수 있는 총 무게 + 1] 크기로 선언해주면 됨

각 배열의 값은 n번째 물건을 선택하지 않았을 때, n번째 물건을 선택했을 때의 max 값임

 

대략적으로 기억은 났는데, 배열 구조 짜는게 헷갈린다

어떤걸 기준으로 크기를 설정해야하고, 어떤 값이 필요한지 정확하게 몰라서 그런것 같다

 

다시 감을 잡아보기로!