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

문제

---

생각하기

---

• 배낭문제이다.

• DP와 메모이제이션을 활용해서 풀이한다.

동작

결과

코드

---

Kotlin

Top-Down

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

// input
private lateinit var br: BufferedReader

// variables
private var N = 0
private var K = 0
private lateinit var arr: Array<Thing>
private lateinit var memo: Array<Array<Int?>> // memo[N + 1][K + 1] = value

private data class Thing(var weight: Int = 0, var value: 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(N - 1, K))
    return sb.toString()
} // End of solve()

private fun knapsack(n: Int, k: Int): Int {
    if (n < 0 || k <= 0) return 0

    if (memo[n][k] != null) return memo[n][k]!!

    // 물건을 배낭에 넣지 않고 통과
    memo[n][k] = knapsack(n - 1, k)

    // 다음 물건을 배낭에 넣을 수 있는지 확인 후
    // 넣을 수 있을 경우에는 집어 넣음
    if (k - arr[n].weight >= 0) {
        memo[n][k] = memo[n][k]!!.coerceAtLeast(knapsack(n - 1, k - arr[n].weight) + arr[n].value)
    }

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

private fun input() {
    StringTokenizer(br.readLine()).run {
        N = nextToken().toInt()
        K = nextToken().toInt()
    }

    arr = Array(N) { Thing() }
    for (i in 0 until N) {
        StringTokenizer(br.readLine()).run {
            arr[i] = Thing(
                nextToken().toInt(),
                nextToken().toInt()
            )
        }
    }

    memo = Array(N + 1) { Array(K + 1) { null } }
} // End of input()

Bottom-Up

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

// input
private lateinit var br: BufferedReader

// variables
private var N = 0
private var K = 0
private lateinit var arr: Array<Thing>
private lateinit var memo: Array<Array<Int?>> // memo[N + 1][K + 1] = value

private data class Thing(var weight: Int = 0, var value: 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(N - 1, K))
    return sb.toString()
} // End of solve()

private fun knapsack(n: Int, k: Int): Int {
    if (n < 0 || k <= 0) return 0

    if (memo[n][k] != null) return memo[n][k]!!

    // 물건을 배낭에 넣지 않고 통과
    memo[n][k] = knapsack(n - 1, k)

    // 다음 물건을 배낭에 넣을 수 있는지 확인 후
    // 넣을 수 있을 경우에는 집어 넣음
    if (k - arr[n].weight >= 0) {
        memo[n][k] = memo[n][k]!!.coerceAtLeast(knapsack(n - 1, k - arr[n].weight) + arr[n].value)
    }

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

private fun input() {
    StringTokenizer(br.readLine()).run {
        N = nextToken().toInt()
        K = nextToken().toInt()
    }

    arr = Array(N) { Thing() }
    for (i in 0 until N) {
        StringTokenizer(br.readLine()).run {
            arr[i] = Thing(
                nextToken().toInt(),
                nextToken().toInt()
            )
        }
    }

    memo = Array(N + 1) { Array(K + 1) { null } }
} // End of input()