[BOJ] 2184 김치 배달 - P3

문제풀이

1. 도시들과 김치 공장을 하나의 배열에 넣고 오름차순 정렬한다.
2. dp[방문한 가장 왼쪽 인덱스][방문한 가장 오른쪽 인덱스][현재 위치(0: 왼쪽 인덱스, 1: 오른쪽 인덱스)] = 최소값으로 두고 dp테이블을 채워나간다.

---

주의사항

---

소요시간

35분

---

package 백준.Platinum.P3.p2184_김치배달

import kotlin.math.abs

const val IMPOSSIBLE = Long.MAX_VALUE shr 2

fun main() {
    val (N, L) = readln().trim().split(" ").map(String::toInt)
    val arr = IntArray(N + 1).apply { this[0] = L }
    for (i in 1..N) {
        arr[i] = readln().toInt()
    }
    arr.sort()
    val startIdx = arr.indexOf(L)
    val dp = Array(N + 1) { Array(N + 1) { LongArray(2) { IMPOSSIBLE } } }
    dp[startIdx][startIdx][0] = 0
    dp[startIdx][startIdx][1] = 0
    for (i in 1..N) {
        for (l in 0..(N - i)) {
            val r = l + i
            if (dp[l + 1][r][0] != IMPOSSIBLE) dp[l][r][0] =
                minOf(dp[l][r][0], dp[l + 1][r][0] + abs(arr[l] - arr[l + 1]).toLong() * (N - i + 1))
            if (dp[l + 1][r][1] != IMPOSSIBLE) dp[l][r][0] =
                minOf(dp[l][r][0], dp[l + 1][r][1] + abs(arr[l] - arr[r]).toLong() * (N - i + 1))
            if (dp[l][r - 1][0] != IMPOSSIBLE) dp[l][r][1] =
                minOf(dp[l][r][1], dp[l][r - 1][0] + abs(arr[r] - arr[l]).toLong() * (N - i + 1))
            if (dp[l][r - 1][1] != IMPOSSIBLE) dp[l][r][1] =
                minOf(dp[l][r][1], dp[l][r - 1][1] + abs(arr[r] - arr[r - 1]).toLong() * (N - i + 1))
        }
    }
    println(dp[0][N].min())
}

https://github.com/TaeGN/Algorithm/blob/master/src/%EB%B0%B1%EC%A4%80/Platinum/P3/p2184_%EA%B9%80%EC%B9%98%EB%B0%B0%EB%8B%AC/p2184_%EA%B9%80%EC%B9%98%EB%B0%B0%EB%8B%AC.kt

---

문제링크

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