[백준] 1149번: RGB거리 - Kotlin[코틀린]

문제

 

1149번: RGB거리

 

---

풀이

 

 이 문제는 3가지 dp배열을 만들고 각각 현재 줄에서 R, G, B를 선택하는 경우를 저장해주는 것으로 해결할 수 있다. 예를 들어 N번 줄에서 R를 선택할 경우에는 N - 1번 줄에서는 G나 B를 선택해야하고 둘 중에서 더 적은 비용의 숫자를 골라 현재 줄의 R을 선택하는 비용과 합쳐준 비용을 dpR배열에 저장해준다.

 

R	G	B
26	40	83
49	60	57
13	89	99

 이 경우에서 dp배열들은 dpR[0] = 26, dpG[0] = 40, dpB[0] = 83로 초기화를 해준다. 그리고 적은 비용을 선택해나가면 된다.

 

dpR[1] = dpG[0] + arr[1][0] = 40 + 49 = 89

dpG[1] = dpR[0] + arr[1][1] = 26 + 60 = 86

dpB[1] = dpR[0] + arr[1][2] = 26 + 57 = 83

 

dpR[2] = dpB[1] + arr[2][0] = 83 + 13 = 96

dpG[2] = dpB[1] + arr[2][1] = 83 + 89 = 172

dpB[2] = dpG[1] + arr[2][2] = 86 + 99 = 185

 

 이런 방식으로 dp 배열들을 채워가고, 가장 적은 비용을 선택한 경우를 출력해주면 된다.

---

코드

 

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

fun main() {
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()

    val num = br.readLine().toInt()
    val arr = Array(num) { IntArray(3) }
    val dpR = IntArray(num)
    val dpG = IntArray(num)
    val dpB = IntArray(num)

    for(i in 0 until num) {
        val line = StringTokenizer(br.readLine())
        for(j in 0 until 3) {
            arr[i][j] = line.nextToken().toInt()
        }
    }

    dpR[0] = arr[0][0]
    dpG[0] = arr[0][1]
    dpB[0] = arr[0][2]

    for(i in 1 until num) {
        dpR[i] = min(dpG[i-1], dpB[i-1]) + arr[i][0]
        dpG[i] = min(dpR[i-1], dpB[i-1]) + arr[i][1]
        dpB[i] = min(dpR[i-1], dpG[i-1]) + arr[i][2]
    }

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

    bw.write("$min")
    bw.flush()
    bw.close()
    br.close()
}