[백준/BOJ] 1149번: RGB거리

문제

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

1149번: RGB거리

해설

다른 알고리즘에 비해 DP에 취약한 것 같아 쉬운 문제부터 풀어보자라는 마음으로 풀어보았다.

이 문제는 어떻게 풀어야할까 고민하던 중 문제의 조건을 다시 한번 읽어보니 힌트를 찾을 수 있었다.

문제에는 3개의 조건이 있지만 결론적으로는 n번째 집은 n-1번째 집과 n+1번째 집과의 색이 달라야 한다는 것이다.

 

예를 들어 현재 위치의 집을 빨간색으로 하고 싶다면 이전 집은 초록 또는 파랑이어야 한다는 것이다.

이를 최솟값으로 하기 위해서는 초록집과 파랑집 중 비용이 덜 드는 집을 선택하면 되는 것이다.

 

따라서 우리는 현재 집을 어떤 색으로 하냐에 따라 이전 집들의 색을 정할 수 있게 된다.

그럼 현재 집의 색은 어떻게 정할까라는 생각이 들 것이다.

뭐 별거있나? 그냥 다 칠해보자.

dp라는 배열이 있을 때 dp[i][0]에는 빨간색으로 칠할 때, dp[i][1]에는 초록색으로 칠할 때, dp[i][2]에는 파랑색으로 칠할 때를 저장해주자.

 

위의 색상을 정하는 점화식을 다음과 같이 된다.

// arr은 각 색상에 따른 비용을 저장해둔 배열

dp[i][0] = minOf(dp[i-1][1], dp[i-1][2]) + arr[i][0]
dp[i][1] = minOf(dp[i-1][0], dp[i-1][2]) + arr[i][1]
dp[i][2] = minOf(dp[i-1][0], dp[i-1][1]) + arr[i][2]

결론적으로 dp[[n][0], dp[n][1], dp[n][2] 중에 가장 작은 비용이 조건에 맞게 칠한 것 중 최솟값이 된다,

코드

fun main() {
    val n = readLine()!!.toInt()
    val arr = Array(n + 1) { IntArray(3) }
    val dp = Array(n + 1) { IntArray(3) }


    repeat(n) { i ->
        arr[i + 1] = readLine()!!.split(" ").map { it.toInt() }.toIntArray()
    }

    for(i in 1 .. n) {
        dp[i][0] = minOf(dp[i-1][1], dp[i-1][2]) + arr[i][0]
        dp[i][1] = minOf(dp[i-1][0], dp[i-1][2]) + arr[i][1]
        dp[i][2] = minOf(dp[i-1][0], dp[i-1][1]) + arr[i][2]
    }

    println(minOf(dp[n][0], minOf(dp[n][1], dp[n][2])))
}