백준 1149 RGB거리 DP Kotlin

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

1149번: RGB거리

 

정답 코드

class RGB{
    var N = 0
    lateinit var Costs:MutableList<MutableList<Int>>
    val colors = List(3) {
        when (it) {
            0 -> listOf(1, 2)
            1 -> listOf(0, 2)
            2 -> listOf(0, 1)
            else -> throw IllegalArgumentException("Invalid index")
        }
    }
    fun solution(){
        N = readln().toInt()
        Costs = MutableList(N){ mutableListOf() }
        for(i in 0 until N){
            var rgb = readln().split(" ").map{ it.toInt() }
            Costs[i].addAll(rgb)
        }

        var dp = MutableList(N){ MutableList(3) {0} }
        dp[N-1] = Costs[N-1]

        for(i in N-2 downTo 0){
            for(j in 0 until 3){
                dp[i][j] = minOf(dp[i+1][colors[j][0]], dp[i+1][colors[j][1]]) + Costs[i][j]
            }
        }
        var answer = minOf(dp[0][0], dp[0][1], dp[0][2])
        println(answer)
    }
}

fun main(){
    var S = RGB()
    S.solution()
}

 

풀이

N: 집의 갯수

dp[i][color] : N-1 ~ i 번째까지의 집을 color(R, G, B 중 하나)로 칠하는 비용의 최솟값

color: 0, 1, 2 // 각각 R, G, B

dp[i][color0] = min(dp[i+1][color1], dp[i+1][color2]) + Costs[i][color0]

Costs[i][color0]: i번째집을 color0로 칠하는데 드는 비용

answer: min(dp[0][0], dp[0][1], dp[0][2])

EX)

3
26 40 83
49 60 57
13 89 99

dp	0:R	1:G	2:B
0	26 + min(73, 70) = 96	40 + min(138, 70) = 119	83 + min(138, 73) = 156
1	49 + min(89, 99) = 138	60 + min(13, 99) = 73	57 + min(13, 89) = 70
2	13	89	99

answer: min(96, 119, 156) => 96