[백준] RGB거리 (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보다 작거나 같은 자연수이다.

출력

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

테스트 케이스

입력	출력
3 26 40 83 49 60 57 13 89 99	96

문제 풀이1 (KOTLIN)DP : Top-Down)

val red = 0
val green = 1
val blue = 2

var houses = 0
var dp = arrayOf<IntArray>()
var cost = arrayOf<IntArray>()

fun main() = with(System.`in`.bufferedReader()) {
    houses = readLine().toInt()
    dp = Array(houses) { IntArray(3) }
    cost = Array(houses) { IntArray(3) }

    repeat(houses) {
        cost[it] = readLine()
            .split(" ")
            .map { value ->
                value.toInt()
            }
            .toIntArray()
    }

    val min = IntArray(3) { topDown(0, it) }
    println(min.min())
}

fun topDown(depth: Int, color: Int): Int {
    if (depth == houses) return 0
    if (dp[depth][color] != 0) return dp[depth][color]

    var colorArr = IntArray(3) { Int.MAX_VALUE }

    if (color != red) colorArr[red] = topDown(depth + 1, red) + cost[depth][color]
    if (color != green) colorArr[green] = topDown(depth + 1, green) + cost[depth][color]
    if (color != blue) colorArr[blue] = topDown(depth + 1, blue) + cost[depth][color]

    dp[depth][color] = colorArr.min()!!
    return dp[depth][color]
}

문제 풀이 (KOTLIN)(DP : Bottom-Up)

import kotlin.math.min

var br = System.`in`.bufferedReader()

fun main() {
    println(bottomUp(br.readLine().toInt()))
    br.close()
}

fun bottomUp(houses: Int): Int {
    var dp = Array(houses) { IntArray(3) }
    var cost = Array(houses) { IntArray(3) }

    repeat(houses) {
        cost[it] = br.readLine()
            .split(" ")
            .map { value ->
                value.toInt()
            }
            .toIntArray()
    }

    dp[0][0] = cost[0][0]
    dp[0][1] = cost[0][1]
    dp[0][2] = cost[0][2]

    for (i in 1 until houses) {
        dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + cost[i][0]
        dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + cost[i][1]
        dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + cost[i][2]
    }

    return dp[cost.size - 1].min()!!
}

문제 풀이 (KOTLIN)

let N = Int(readLine()!)!
var dp = Array(repeating: [Int](repeating: 0, count: 3), count: N + 1)
var arr = Array(repeating: [Int](repeating: 0, count: 3), count: N + 1)

for i in 0..<N {
    let cost = readLine()!.split(separator: " ").map { Int($0)! }
    for j in 0..<3 {
      arr[i + 1][j] = cost[j]
    }
}

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

print(dp[N].min()!)