백준 16493번
https://www.acmicpc.net/problem/16493
배낭 문제이다.
메모이제이션, DP를 사용해서 최적화 한다.
import java.io.File
import java.util.StringTokenizer
// input
private var br = System.`in`.bufferedReader()
// variables
private var N = 0
private var M = 0
private lateinit var memo: Array<IntArray>
private lateinit var arr: 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, M))
return sb.toString()
} // End of solve()
private fun topDown(n: Int, m: Int): Int {
if (n == 0 || m == 0) return 0
if (memo[n][m] != -1) return memo[n][m]
if (n - arr[m - 1][0] >= 0) {
memo[n][m] = Math.max(memo[n][m], Math.max(topDown(n, m - 1), topDown(n - arr[m - 1][0], m - 1) + arr[m - 1][1]))
} else {
memo[n][m] = topDown(n, m - 1)
}
return memo[n][m]
} // End of topDown()
private fun input() {
var st = StringTokenizer(br.readLine())
N = st.nextToken().toInt()
M = st.nextToken().toInt()
memo = Array(N + 1) {
IntArray(M + 1) { -1 }
}
arr = Array(M) {
st = StringTokenizer(br.readLine())
IntArray(2) {
st.nextToken().toInt()
}
}
} // End of input()