[백준] 1149. RGB거리 (Kotlin)

문제

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

1149번: RGB거리

 

풀이

0. 문제 해석

• 1번 집의 색은 2번 집의 색과 같지 않아야 한다.
• N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.
• i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.

 

위 조건을 요약하면 인접한 집과 다른 색으로 칠해야 한다는 뜻이다.

 

여기서 DP를 사용할 수 있는데

1번째 집부터 n번째 집까지 탐색하면서 현재 위치의 집까지 각각 R,G,B 로 칠하는 최소 비용을 저장한다.

 

첫 번째 집을 R,G,B로 칠하는 최소 비용은 각각 r,g,b 값일 것이다.

두 번째 집 부터는 예를 들어 현재 집을 R로 칠하려고 한다면 자신보다 한 칸 전의 집 색깔을 G,B 로 칠한 최소 비용을 가져와 현재 위치의 비용을 더하면 된다.

 

 dpR[i] = min(dpG[i - 1], dpB[i - 1]) + r[i]
 dpG[i] = min(dpR[i - 1], dpB[i - 1]) + g[i]
 dpB[i] = min(dpR[i - 1], dpG[i - 1]) + b[i]

 

 

결론적으로 점화식은 위와 같다.

 

1. 전체 코드

// [백준] 1149. RGB거리 (Kotlin)
import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*
import kotlin.math.min

fun main() = with(BufferedReader(InputStreamReader(System.`in`))){
    val n = readLine().toInt()

    // 입력받은 비용
    val r = arrayListOf<Int>()
    val g = arrayListOf<Int>()
    val b = arrayListOf<Int>()

    // 최소 비용
    val dpR = Array(n){ 0 }
    val dpG = Array(n){ 0 }
    val dpB = Array(n){ 0 }

    // 입력
    repeat(n){
        val str = StringTokenizer(readLine())
        r.add(str.nextToken().toInt())
        g.add(str.nextToken().toInt())
        b.add(str.nextToken().toInt())
    }

    // 처음 값은 항상 최대값
    dpR[0] = r[0]
    dpG[0] = g[0]
    dpB[0] = b[0]

    for(i in 1 until n){
        dpR[i] = min(dpG[i - 1], dpB[i - 1]) + r[i]
        dpG[i] = min(dpR[i - 1], dpB[i - 1]) + g[i]
        dpB[i] = min(dpR[i - 1], dpG[i - 1]) + b[i]
    }

    val result = min(dpR[n - 1],min(dpG[n - 1], dpB[n - 1]))

    println(result)
}