백준 1535번
https://www.acmicpc.net/problem/1535
Knapsack 문제이다.
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
배열에 저장하도록 한다.
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()