백준 17404번
https://www.acmicpc.net/problem/17404

문제

---

생각하기

---

• DP 문제이다.

• RGB거리 1이랑 거의 비슷한데 조금 꼬였다.

동작

처음 집의 색상이 마지막 N번째 집의 색생과 같을 수 없으므로
처음 집의 색상 3개 마다 새로운 memo배열을 생성해서 최소값을 가져와야 한다.

여기서 핵심은 1번째 집은 N번째 집의 색상과 같을 수 없음이다.

private fun DP(): Int {
    var ans = INF

    repeat(3) { i ->
        when (i) {
        	// 각 처음집의 색상이 선택되면 나머지 집은 INF값으로 초기화
            0 -> {
                memo[0][0] = colors[0].red
                memo[0][1] = INF
                memo[0][2] = INF
            }

            1 -> {
                memo[0][0] = INF
                memo[0][1] = colors[0].green
                memo[0][2] = INF
            }

            2 -> {
                memo[0][0] = INF
                memo[0][1] = INF
                memo[0][2] = colors[0].blue
            }
        }


        for (j in 1 until N) {
            memo[j][0] = min(memo[j - 1][1], memo[j - 1][2]) + colors[j].red
            memo[j][1] = min(memo[j - 1][0], memo[j - 1][2]) + colors[j].green
            memo[j][2] = min(memo[j - 1][0], memo[j - 1][1]) + colors[j].blue
        }

        for (j in 0 until 3) {
            if (i == j) {
                // 처음집의 색깔과 끝의 집 색깔은 같을 수 없으므로 continue
                continue
            }
            // 각 처음 집에 색칠한 집을 기준으로
            // 가장 끝에 있는 값 중에서 최소값을 선택
            ans = min(ans, memo[N - 1][j])
        }
    }

    return ans
} // End of DP()

결과

코드

---

Kotlin

import java.io.*
import java.util.*
import kotlin.math.min

// input
private lateinit var br: BufferedReader

// variables
private const val INF = Int.MAX_VALUE / 4
private var N = 0
private lateinit var memo: Array<IntArray> // N번째의 색상별 최소비용
private lateinit var colors: Array<Color>

private data class Color(var red: Int = 0, var green: Int = 0, var blue: Int = 0)

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

    input()

    bw.write(solve())
    bw.close()
} // End of main()

private fun solve(): String {
    val sb = StringBuilder()

    sb.append(DP())
    return sb.toString()
} // End of solve()

private fun DP(): Int {
    var ans = INF

    repeat(3) { i ->
        when (i) {
            0 -> {
                memo[0][0] = colors[0].red
                memo[0][1] = INF
                memo[0][2] = INF
            }

            1 -> {
                memo[0][0] = INF
                memo[0][1] = colors[0].green
                memo[0][2] = INF
            }

            2 -> {
                memo[0][0] = INF
                memo[0][1] = INF
                memo[0][2] = colors[0].blue
            }
        }


        for (j in 1 until N) {
            memo[j][0] = min(memo[j - 1][1], memo[j - 1][2]) + colors[j].red
            memo[j][1] = min(memo[j - 1][0], memo[j - 1][2]) + colors[j].green
            memo[j][2] = min(memo[j - 1][0], memo[j - 1][1]) + colors[j].blue
        }

        for (j in 0 until 3) {
            if (i == j) continue
            ans = min(ans, memo[N - 1][j])
        }
    }

    return ans
} // End of DP()

private fun input() {
    N = br.readLine().toInt()

    memo = Array(N + 1) { IntArray(3) }
    colors = Array(N + 1) { Color(0, 0, 0) }

    colors = Array(N + 1) { Color() }
    for (i in 0 until N) {
        StringTokenizer(br.readLine()).run {
            colors[i] = Color(
                nextToken().toInt(),
                nextToken().toInt(),
                nextToken().toInt(),
            )
        }
    }
} // End of input()