백준 29756번
https://www.acmicpc.net/problem/29756

문제

---

생각하기

---

• 배낭, DP 문제이다.
  • memoization을 사용해서 TopDown으로 구현했다.

동작

결과

코드

---

Kotlin

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

// input
private lateinit var br: BufferedReader

// variables
private const val MAX_HEALTH = 100
private var N = 0
private var K = 0
private lateinit var scores: IntArray
private lateinit var healths: IntArray
private lateinit var memo: Array<IntArray>

fun main() {
    br = BufferedReader(InputStreamReader(System.`in`))
    val bw = BufferedWriter(OutputStreamWriter(System.out))

    input()

    bw.write(solve())
    bw.close()
} // End of main()

private fun solve(): String {
    val sb = StringBuilder()

    sb.append(knapsack(N, MAX_HEALTH))
    return sb.toString()
} // End of solve()

private fun knapsack(n: Int, health: Int): Int {
    if (n == 0) return 0
    if (memo[n][health] != -1) return memo[n][health]

    val newHealth = MAX_HEALTH.coerceAtMost(health + K)

    // 통과
    memo[n][health] = knapsack(n - 1, newHealth)
    
    if (newHealth >= healths[n]) {
        memo[n][health] = memo[n][health].coerceAtLeast(knapsack(n - 1, newHealth - healths[n]) + scores[n])
    }

    return memo[n][health]
} // End of knapsack()

private fun input() {
    StringTokenizer(br.readLine()).run {
        N = nextToken().toInt() // 곡의 전체 구간의 수
        K = nextToken().toInt() // 회복하는 체력의 양
    }

    scores = IntArray(N + 1)
    StringTokenizer(br.readLine()).run {
        for (i in 1..N) {
            scores[i] = nextToken().toInt()
        }
    }

    healths = IntArray(N + 1)
    StringTokenizer(br.readLine()).run {
        for (i in 1..N) {
            healths[i] = nextToken().toInt()
        }
    }

    memo = Array(N + 1) { IntArray(MAX_HEALTH + 1) { -1 } }
} // End of input()