[BOJ] 2419 사수아탕 - P1

문제풀이

1. dp[방문한 최소 인덱스][방문한 최대 인덱스][현재 위치(0: 왼쪽, 1: 오른쪽)]
2. 방문할 사탕 바구니 개수를 (1 ~ N)으로 정하고, N번 반복하며 최대값을 구한다.

---

주의사항

1. 사탕 바구니에 무한대가 아닌 m개의 사탕이 있으므로 방문하는 도중에 0개가 될 수 있다. 즉, 각 지점에서의 최대값이 전체의 최대값이 아닐 수 있다.

---

소요시간

1시간 30분

---

package 백준.Platinum.P1.p2419_사수아탕

import kotlin.math.abs

const val EMPTY = -1
fun main() {
    val (N, M) = readln().trim().split(" ").map(String::toInt)
    val xArr = IntArray(N + 1)
    for (i in 1..N) {
        xArr[i] = readln().toInt()
    }
    xArr.sort()
    val S = xArr.indexOf(0)
    val dp = Array(N + 1) { Array(N + 1) { Array(2) { EMPTY } } }
    fun dp(count: Int, l: Int = S, r: Int = S, pos: Int = 0): Int {
        if (count == 0) return 0
        if (dp[l][r][pos] != EMPTY) return dp[l][r][pos]
        val cur = if (pos == 0) l else r
        dp[l][r][pos] = 0
        if (l > 0) dp[l][r][pos] =
            maxOf(dp[l][r][pos], dp(count - 1, l - 1, r, 0) + M - count * abs(xArr[cur] - xArr[l - 1]))
        if (r < N) dp[l][r][pos] =
            maxOf(dp[l][r][pos], dp(count - 1, l, r + 1, 1) + M - count * abs(xArr[cur] - xArr[r + 1]))
        return dp[l][r][pos]
    }

    var result = 0
    for (i in 1..N) {
        dp.forEach { r -> r.forEach { c -> c.fill(EMPTY) } }
        result = maxOf(result, dp(i))
    }
    println(result)
}

https://github.com/TaeGN/Algorithm/blob/master/src/%EB%B0%B1%EC%A4%80/Platinum/P1/p2419_%EC%82%AC%EC%88%98%EC%95%84%ED%83%95/p2419_%EC%82%AC%EC%88%98%EC%95%84%ED%83%95.kt

---

문제링크

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

---

회고

처음에는 그렇게 어려운 문제는 아니라 생각했는데, 문제를 풀려고 보니 시간이 m이상이 되었을때 어떻게 처리해야할지 막막했다. n개의 지점을 방문하는 코드를 그냥 짜면 틀렸습니다가 나오고, 부분 문제로 나눠서 각각의 최대값중에서 최대값을 구하는 형식으로 답을 구해야 했다.