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

문제

---

생각하기

---

• DP의 기본적인 개념 문제이다.

• 메모이제이션을 이용하여 최적화를 진행한다.

• 점화식을 세울 수 있어야 한다.
  

동작

먼저 규칙을 간단하게 이해하는게 중요한다.
문제에서 주어진 규칙을 쉽게 풀어보면 그냥 이전에 칠해졌던 색깔은 다시 사용하지마라~ 하고 겹치는 색의 집이 연속으로 나오지 않게 만들면 된다.

이전의 집이 빨간색일 경우 다음집은 초록색과 파란색으로 선택하면 된다.

private fun DP() {
    for (i in 2..N) {
        memo[i][0] = min(memo[i - 1][1], memo[i - 1][2]) + red[i]
		// 빨간색으로 칠했을 떄 최소 비용 구하기,
        // 빨간색 최소 비용을 구하려면 이전에 집이 빨간색이 아닌 집 중에 선택해야 한다.
        // 초록색과 파란색으로 칠해진 집 중에 최소값을 선택한다
        
        memo[i][1] = min(memo[i - 1][0], memo[i - 1][2]) + green[i] // 초록색으로 칠했을 때 최소 비용
        memo[i][2] = min(memo[i - 1][0], memo[i - 1][1]) + blue[i] // 파란색으로 칠했을 때 최소 비용
    }
} // End of DP()

memo에 각 i 번째 집의 색깔별 최소비용을 저장해둔다.

빨간색을 예로 하나 들자면 2번째 집을 색칠할 때 최소비용을 구하는 과정은
이전의 첫 번째 집이 파란색으로 칠해진 경우의 비용과 초록색으로 칠해진 비용중에서 싼 비용을 하나 선택해서 오면 된다.

그리고 여기서 i번째 집의 빨간색 색칠 비용인 red[i]를 더하면 i번째 집이 빨간색으로 색칠될 때 최소비용을 구할 수 있게 된다.

결과

코드

---

Kotlin

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

// input
private lateinit var br: BufferedReader

// variables
private var N = 0

private lateinit var memo: Array<IntArray> // i번쨰 집을 j색으로 칠할 때의 최소비용을 저장
private lateinit var red: IntArray
private lateinit var green: IntArray
private lateinit var blue: IntArray

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()
    memo[1][0] = red[1]
    memo[1][1] = green[1]
    memo[1][2] = blue[1]
    DP()

    sb.append(min(memo[N][0], min(memo[N][1], memo[N][2])))
    return sb.toString()
} // End of solve()

private fun DP() {
    for (i in 2..N) {
        memo[i][0] = min(memo[i - 1][1], memo[i - 1][2]) + red[i]
        memo[i][1] = min(memo[i - 1][0], memo[i - 1][2]) + green[i] // 초록색으로 칠했을 때 최소 비용
        memo[i][2] = min(memo[i - 1][0], memo[i - 1][1]) + blue[i] // 파란색으로 칠했을 때 최소 비용
    }
} // End of DP()

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

    memo = Array(N + 1) { IntArray(3) }
    red = IntArray(N + 1)
    green = IntArray(N + 1)
    blue = IntArray(N + 1)

    for (i in 1..N) {
        StringTokenizer(br.readLine()).run {
            red[i] = nextToken().toInt()
            green[i] = nextToken().toInt()
            blue[i] = nextToken().toInt()
        }
    }
} // End of input()