[백준 1149번] RGB거리 - Kotlin

[백준 1149번] RGB거리 - Kotlin

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

---

문제

• RGB거리에는 집이 N개 있다.
• 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.
• 집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다.
• 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.
  • 1번 집의 색은 2번 집의 색과 같지 않아야 한다.
  • N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.
  • i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.

---

입력

• 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다.
• 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다.
• 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다.

---

출력

• 첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.

---

풀이

import kotlin.math.min

private class Solution1149 {
    fun solution(map: Array<Triple<Int, Int, Int>>): Int {
        val dp = Array(3) { IntArray(map.size) }
        dp[0][0] = map[0].first
        dp[1][0] = map[0].second
        dp[2][0] = map[0].third

        for (i in 1 until map.size) {
            dp[0][i] = map[i].first + minOf(dp[1][i - 1], dp[2][i - 1])
            dp[1][i] = map[i].second + minOf(dp[0][i - 1], dp[2][i - 1])
            dp[2][i] = map[i].third + minOf(dp[0][i - 1], dp[1][i - 1])
        }

        return min(dp[0][map.lastIndex], min(dp[1][map.lastIndex], dp[2][map.lastIndex]))
    }
}

private fun main() {
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()

    val n = br.readLine().toInt()
    val map = Array(n) {
        val (r, g, b) = br.readLine().split(" ").map(String::toInt)

        Triple(r, g, b)
    }

    bw.append("${Solution1149().solution(map)}\n")
    bw.flush()

    br.close()
    bw.close()
}