[BOJ] 16297 Eating Everything Efficiently - P5

문제풀이

1. dp[시작 인덱스] = 시작 인덱스에서 시작하여 얻을 수 있는 최대 만족도로 정의한다.
2. 현재 지점을 방문할지 안할지를 구분하며 최대값을 기록한다.
   • maxOf(현재 인덱스 만족도 + (현재 이후에서 얻을 수 있는 최대 만족도 / 2), 현재 이후에서 얻을 수 있는 최대 만족도)

---

주의사항

---

소요시간

25분

---

package 백준.Platinum.P5.p16297_EatingEverythingEfficiently

const val EMPTY = -1.0
const val MIN_VALUE = Double.MIN_VALUE
fun main() {
    val (N, M) = readln().trim().split(" ").map(String::toInt)
    val iArr = readln().trim().split(" ").map(String::toInt)
    val outLists = List(N) { mutableListOf<Int>() }
    repeat(M) { readln().trim().split(" ").map(String::toInt).let { outLists[it[0]].add(it[1]) } }
    val dp = DoubleArray(N) { EMPTY }
    fun dfs(from: Int = 0): Double {
        if (dp[from] != EMPTY) return dp[from]
        var nextValue = 0.0
        for (to in outLists[from]) {
            nextValue = maxOf(nextValue, dfs(to))
        }
        return (maxOf(iArr[from] + nextValue / 2, nextValue)).also { dp[from] = it }
    }
    println(dfs())
}

https://github.com/TaeGN/Algorithm/blob/master/src/%EB%B0%B1%EC%A4%80/Platinum/P5/p16297_EatingEverythingEfficiently/p16297_EatingEverythingEfficiently.kt

---

문제링크

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