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

문제

---

생각하기

---

• 배낭 문제이다.

• 메모이제이션을 활용해서 문제를 풀었다.
  

동작

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

    memo[n][t] = knapsack(n - 1, t)
    if (t >= arr[n].day) {
        memo[n] [t] = Math.max(memo[n][t], knapsack(n - 1, t - arr[n].day) + arr[n].penalty)

    }

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

배낭 문제의 대표적인 특징으로 선택하지 않고 통과, 선택 2가지만 잘 고려하면 된다.

memo[n][t] = knapsack(n - 1, t) 이 선택하지 않는 부분이다.

    if (t >= arr[n].day) {
        memo[n] [t] = Math.max(memo[n][t], knapsack(n - 1, t - arr[n].day) + arr[n].penalty)

    }
  
	남은 일수로 문제를 푸는데 걸리는 시간이 가능 할 때, 걸리는 시간에 벌금을 더한다.

문제에서는 "최소의 벌금"을 구하라고 되어 있지만, 코드에서는 실제로 "피해야 하는 최대의 벌금"을 구하고 있다.

이렇게 하면 "전체 벌금 - 피해야 하는 최대의 벌금 = 내야 하는 최소의 벌금"이라는 관계가 성립하게 된다.

전체 벌금 : 모든 문제에 대한 벌금의 합계입니다. 제출 기한 내에 어떤 문제를 풀든 절대 변하지 않는 값이다.

그래서 결과는 sum - knapsack(N, T)으로 구할 수 있다.

결과

코드

---

Kotlin

Top-Down

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

// input
private lateinit var br: BufferedReader

// variables
private var N = 0
private var T = 0
private var sum = 0
private lateinit var arr: Array<Problem>
private lateinit var memo: Array<IntArray>

private data class Problem(var day: Int = 0, var penalty: 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(sum - knapsack(N, T))
    return sb.toString()
} // End of solve()

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

    memo[n][t] = knapsack(n - 1, t)
    if (t >= arr[n].day) {
        memo[n][t] = Math.max(memo[n][t], knapsack(n - 1, t - arr[n].day) + arr[n].penalty)

    }

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

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

    arr = Array(N + 1) { Problem() }
    for (i in 1..N) {
        StringTokenizer(br.readLine()).run {
            arr[i] = Problem(
                nextToken().toInt(),
                nextToken().toInt()
            )
        }
        sum += arr[i].penalty
    }

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

Bottom-Up

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

// input
private lateinit var br: BufferedReader

// variables
private var N = 0
private var T = 0
private var sum = 0

private lateinit var arr: Array<Problem>
private lateinit var memo: Array<IntArray>

data class Problem(var day: Int = 0, var penalty: 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()

    knapsack()
    sb.append(sum - memo[N][T])
    return sb.toString()
} // End of solve()

private fun knapsack() {
    for (i in 1..N) {
        for (j in 1..T) {
            memo[i][j] = memo[i - 1][j]
            if (arr[i].day <= j) {
                memo[i][j] = memo[i][j].coerceAtLeast(memo[i - 1][j - arr[i].day] + arr[i].penalty)
            }
        }
    }
} // End of knapsack

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

    arr = Array(N + 1) { Problem() }
    for (i in 1..N) {
        StringTokenizer(br.readLine()).run {
            arr[i] = Problem(
                nextToken().toInt(),
                nextToken().toInt()
            )
        }

        sum += arr[i].penalty
    }

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