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

문제

---

생각하기

---

• Knapsack 문제이다.

  • DP를 통해서 최적화를 해야한다.
  • 부르트포스도 가능(?)한 것 같다
  • TopDown재귀를 통해서 구현했다.

동작

private fun knapsack(health: Int, idx: Int): Int {
    if (health <= 0 || idx == 0) return 0

    if (memo[health][idx] != -1) return memo[health][idx]

    // 선택하지 않고 그냥 통과
    memo[health][idx] = knapsack(health, idx - 1)

    if (health - claps[idx].health > 0) {
        memo[health][idx] =
            memo[health][idx].coerceAtLeast(knapsack(health - claps[idx].health, idx - 1) + claps[idx].happy)
    }

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

배낭문제 특성을 이용해서 쉽게 풀 수 있다.

선택지가 크게 2개
1. 배낭에 넣지 않는다.
2. 배낭에 넣는다.

이렇게 2개인데, 배낭에 넣지 않는 선택지는
memo[health][idx] = knapsack(health, idx - 1) health를 증가시키지 않고 idx만 1 증가시키게 된다.

두번째 가방에 넣는 선택지에서는, if (health - claps[idx].health > 0) 조건에 health를 빼고 0을 넘게되면, 배낭에 넣게된다.

memo[health][idx].coerceAtLeast(knapsack(health - claps[idx].health, idx - 1) + claps[idx].happy)
이제 재귀를 통해서 빠져나왔을 때 값과, 현재 memo에 저장되어 있는 값 중에 최대값으로 선택해서 다시 memo배열에 저장하도록 한다.

결과

코드

---

Kotlin

Top-Down

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

// input
private lateinit var br: BufferedReader

// variables
private const val MAX_HEALTH = 100
private var N = 0
private lateinit var memo: Array<IntArray>
private lateinit var claps: Array<Clap>

private data class Clap(var health: Int = 0, var happy: Int = 0)

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(MAX_HEALTH, N))
    return sb.toString()
} // End of solve()

private fun knapsack(health: Int, idx: Int): Int {
    if (health <= 0 || idx == 0) return 0

    if (memo[health][idx] != -1) return memo[health][idx]

    // 선택하지 않고 그냥 통과
    memo[health][idx] = knapsack(health, idx - 1)

    if (health - claps[idx].health > 0) {
        memo[health][idx] =
            memo[health][idx].coerceAtLeast(knapsack(health - claps[idx].health, idx - 1) + claps[idx].happy)
    }

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

private fun input() {
    N = br.readLine().toInt()

    memo = Array(MAX_HEALTH + 1) { IntArray(N + 1) { -1 } }
    claps = Array(N + 1) { Clap(0, 0) }

    val st1 = StringTokenizer(br.readLine())
    val st2 = StringTokenizer(br.readLine())

    repeat(N) { idx ->
        claps[idx + 1] = Clap(
            st1.nextToken().toInt(),
            st2.nextToken().toInt()
        )
    }
} // End of input()