백준 29756 - DDR 체력 관리

https://www.acmicpc.net/problem/29756

풀이

각 구간을 플레이할지, 포기할지 선택해야 하는데, 그리디를 사용하기에는 최적의 방법이 없기에 결국 한 구간마다 플레이 또는 포기할지를 다 알아야 한다. 따라서 DP를 활용해 점화식을 세워 반복되는 구간을 제거할 수 있다.

dp [x][y] = x번째 구간에 왔을 때 현재 체력이 y인 경우 최대 점수

위 점화식을 가지고 Top-Down을 활용해 플레이 또는 포기할지를 다 진행하면 된다.

1. 해당 구간을 포기한다. dp[x][y] = answer(x + 1, min(100, y + k))
2. 해당 구간을 플레이할 수 있다면 플레이한다. dp[x][y] = answer(x + 1, min(100, y - hits[x] + k)) + scores[x]

코드

import kotlin.math.min

fun main() {
    val (n, k) = readln().split(" ").map { it.toInt() }

    val scores = readln().split(" ").map { it.toInt() }
    val hits = readln().split(" ").map { it.toInt() }

    val dp = Array(n + 1) { IntArray(101) { -1 } }

    fun answer(x: Int, y: Int): Int {
        if (x == n) {
            return 0
        }

        if (dp[x][y] != -1) return dp[x][y]

        dp[x][y] = answer(x + 1, min(100, y + k))

        if (y - hits[x] >= 0) {
            dp[x][y] = maxOf(dp[x][y], answer(x + 1, min(100, y - hits[x] + k)) + scores[x])
        }

        return dp[x][y]
    }


    println(answer(0, 100))
}