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

문제

---

생각하기

---

• 배낭 문제이다.

• 메모이제이션, DP를 사용해서 최적화 한다.

동작

결과

코드

---

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

// input
private var br = System.`in`.bufferedReader()

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

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

fun main() {
    val bw = System.out.bufferedWriter()

    input()

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

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

    sb.append(topDown(N, T))
    return sb.toString()
} // End of solve()

private fun topDown(n: Int, t: Int): Int {
    if (n == 0 || t == 0) return 0;

    if (memo[n][t] != -1) return memo[n][t]

    if (t - arr[n - 1][0] >= 0) {
        memo[n][t] = Math.max(topDown(n - 1, t), topDown(n - 1, t - arr[n - 1][0]) + arr[n - 1][1])
    } else {
        memo[n][t] = Math.max(memo[n][t], topDown(n - 1, t))
    }

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

private fun input() {
    var st = StringTokenizer(br.readLine())
    N = st.nextToken().toInt()
    T = st.nextToken().toInt()

    arr = Array(N) {
        st = StringTokenizer(br.readLine())
        IntArray(2) {
            st.nextToken().toInt()
        }
    }

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