1149번: RGB거리

문제 출처 : https://www.acmicpc.net/problem/1149

1149번: RGB거리

언어 : Kotlin

 

문제 설명 :

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보다 작거나 같은 자연수이다.
• 첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.

제한 사항 :

• 시간 제한 : 0.5초 (추가 시간 없음)
• 메모리 제한 : 128MB

 

입출력 예 :

입력	출력
3 26 40 83 49 60 57 13 89 99	96
3 1 100 100 100 1 100 100 100 1	3
3 1 100 100 100 100 100 1 100 100	102
6 30 19 5 64 77 64 15 19 97 4 71 57 90 86 84 93 32 91	208
8 71 39 44 32 83 55 51 37 63 89 29 100 83 58 11 65 13 15 47 25 29 60 66 19	253

풀이 : 

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val bw = BufferedWriter(OutputStreamWriter(System.out))

    val n = br.readLine().toInt()
    val dp = Array(n) { IntArray(3) { 0 } }
    repeat(n) {
        br.readLine().also { i ->
            val temp = i.split(" ").map { it.toInt() }
            for (j in 0 .. 2) { dp[it][j] = temp[j] }
        }
    }

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

    bw.write("${minOf(dp[n - 1][0], dp[n - 1][1], dp[n - 1][2])}")
    bw.flush()
    bw.close()
}

 

풀 때 도움을 준 사고방식 : https://www.acmicpc.net/board/view/101509

글 읽기 - 벽느낌