[BOJ/Kotlin] 1149번 RGB거리 : DP

문제 설명

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보다 작거나 같은 자연수이다.

출력

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

문제 풀이 아이디어

1. 입력으로 집의 수와 각 n번째 집을 빨강,초록,파랑으로 색칠 했을 때 발생하는 비용을 담는 배열을 만든다.

2. 점화식 세우기

d[i][0] = i번째 집을 빨강으로 색칠했을 때 최소비용
d[i][1] = i번째 집을 초록으로 색칠했을 때 최소비용
d[i][2] = i번째 집을 파랑으로 색칠했을 때 최소비용 이라 놓는다.

세운 d[i] 설명을 바탕으로 i번째 각 최소비용을 계산하면 

d[i][0] = min(d[i-1][1],d[i-1][2]) + colors[0][i-1]
d[i][1] = min(d[i-1][2],d[i-2][0]) + colors[1][i-1]
d[i][2] = min(d[i-1][0],d[i-2][1]) + colors[2][i-1] 

이렇게 식을 세울 수 있다.

왜냐하면 문제에서 조건으로 i번째 집의 좌우 집에 색칠된 색과 동일한 색으로 i번째 집을 색칠하면 안되기 때문이다.
d[i][0] 은 i번째 집을 빨강으로 색칠한다는 의미로 i-1번째 집은 초록 혹은 파랑으로 색칠되어야한다. 비용의 최솟값이여야 하므로 min(d[i-1][1], d[i-1][2])이고, 해당 i번째 집을 빨강으로 색칠 할 때 드는 비용까지 더해주면 d[i][0]의 값을 구할 수 있다.

코드

import java.io.BufferedReader
import java.io.InputStreamReader
import java.lang.Integer.min

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val N = readLine().toInt() //집의 수
    val colors = Array(3){IntArray(N)} // 집의 수 만큼 빨강,초록,파랑의 비용값 넣는 리스트
    // colors를 담을 때 유의해야 함.
    for (i in 0 until N){
        var input = readLine().split(" ")
        for (j in input.indices){
            colors[j][i] = input[j].toInt() //j번째 color로 i번째 집을 색칠할 때 비용
        }
    }

    val d = Array(N+1){IntArray(3) {0} } //i번째 집을 j번째 color로 색칠할 때 누적 최소비용.
    d[1][0] = colors[0][0] //1번째 집을 0번째 color로 색칠 할때 최소비용
    d[1][1] = colors[1][0]
    d[1][2] = colors[2][0]

    for (i in 2 .. N){
        d[i][0] = min(d[i-1][1],d[i-1][2]) + colors[0][i-1]
        d[i][1] = min(d[i-1][0],d[i-1][2]) + colors[1][i-1]
        d[i][2] = min(d[i-1][0],d[i-1][1]) + colors[2][i-1]
    }
    var min = d[N][0]

    for (i in 0 .. 2){
        if (d[N][i] < min){
            min = d[N][i] // n번째 집까지 색칠 했을 때 최소비용을 구해야하므로, 빨강, 초록, 파랑일 때를 비교해서 min값을 구한다.
        }
    }
    println(min) //n번째 집까지 최소비용을 출력한다. 
}

배운점 

백준 예시의 입력을 잘못해석해서 잘못된 답을 도출했었다. 예시로 해당 문제에 3개의 집이있으면, 

3
26 40 83
49 60 57
13 89 99

1번째 줄이 1번째 집을 각 빨강, 초록, 파랑으로 색칠 할때 드는 비용을 의미하고, 아래로 내려가면서 n번째 집을 색칠 할 때 드는 컬러비용을 의미하는 것이다.

하지만 첫번째 3개의 집만 색칠하는 예시를 보고 26,40,83이 첫번째, 두번째, 세번째 집을 빨강으로 색칠하는 경우라 잘못 이해를 해서 입력을 다시 수정했다. 이 때문인지 colors 배열을 만들어서 입력받는 과정이 매우 헷갈렸다.

다른 코드들을 찾아보면서 입력을 더욱 간소화하고, 메모리 사용도 더욱 적게하는 방법을 알 수 있었다. 코드는 아래와같다. 

import java.io.BufferedReader
import java.io.InputStreamReader
import java.lang.Integer.min

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val N = readLine().toInt() //집의 수
    val R = Array(N) { 0 }
    val G = Array(N) { 0 }
    val B = Array(N) { 0 }
    // colors를 담을 때 유의해야 함.
    for (i in 0 until N) {
        var input = readLine().split(" ")
        R[i] = input[0].toInt() //i번째 집 빨강으로 색칠하는 비용
        G[i] = input[1].toInt() //위와 동일
        B[i] = input[2].toInt() //위와 동일
    }

    val d = Array(N + 1) { IntArray(3) { 0 } } //i번째 집을 j번째 color로 색칠할 때 누적 최소비용.
    d[1][0] = R[0] //1번째 집을 0번째 color로 색칠 할때 최소비용
    d[1][1] = G[0]
    d[1][2] = B[0]

    for (i in 2..N) {
        d[i][0] = min(d[i - 1][1], d[i - 1][2]) + R[i - 1]
        d[i][1] = min(d[i - 1][0], d[i - 1][2]) + G[i - 1]
        d[i][2] = min(d[i - 1][0], d[i - 1][1]) + B[i - 1]
    }
    var min = d[N][0]

    for (i in 0..2) {
        if (d[N][i] < min) {
            min = d[N][i]
        }
    }
    println(min)
}

Colors 라는 배열에 한번에 모든 값을 받지 않고, 각각 index i번째 집을 빨강으로 색칠 할때의 비용들을 모은 R 배열 똑같은 방식으로 초록 G, 파랑 B를 만들어서 입력을 받는 방식이다.

메모리도 더욱 아끼고, 입려자체를 받을 때 헷갈릴 요소를 줄인 코드라 배울 수 있는 코드였다. 

예시가 여러개면 여러 입력 예시들을 보고 입력을 오해하는 일을 줄이도록 해야겠다.