[Kotlin] 백준(BOJ) 1149 RGB거리

문제 전문은 아래 버튼을 눌러 확인하실  수 있습니다.

문제

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

 

출력

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

 

예제 입출력

 

문제 해설

문제를 다시 간단하게 요약하자면, R, G, B 3가지의 색을 최종 비용이 최소가 되고, 이웃한 집끼리 색깔이 같지 않으게되도록 각 집에 배정하는 것이다. 

전형적인 다이나믹 프로그래밍 문제의 유형 중 하나라고 할 수 있겠다. 현재 고려하고 있는 집에 어떤 색을 배정한다고 할 때 그 배정이 최종적으로 최선일지 아닐지 알기 위해서는 맨 끝까지 탐색해야 결정할 수 있다. 

 

때문에 이 탐색을 최대한 빠르고 쉽게 해결하기 위해서는 문제를 나눠 생각하여야 한다. 이를 생각하는 방법에는 재귀 알고리즘을 사용하는 탑 다운 메모이제이션과, 단순히 선형 자료구조를 채우면서 진행하는 바텀 업 타뷸레이션 방식이 있는데 바텀 업 방식으로 설명하도록 하겠다.

 

예제 입출력 1을 기준으로 생각해봤을 때

1번째집의 최솟값은 단순히 R, G, B의 비용 중 최소인 값을 취하면 되므로, R, 26이다.  

하지만 2번째 집까지 포함하는 최솟값을 생각해봤을 때, 1번째 집을 R로 칠하면 안될 수 있다. 이전 집에서 선택한 색상은 다음 집에서 선택할 수 없기 때문이다.

 

예제에는 그렇지 않지만 만약 2번집의 R 색칠 비용이 1이라면 사실 1번째 집에서 비용 40의 G를 색칠하고 2번째 집에서 비용 1만 지불하면 해당 값이 최소이다. 

 

때문에 단순히 최솟값만 취하는 그리디적인 사고가 아닌, 최솟값 후보들을 전부 기록해 뒀다가 실제로 대입해봐야한다. 

여기서 최솟값 후보는 결국 다음을 의미한다. 

이전 집의 각 색깔별 최솟값 + 현재 집의 각 색깔 코스트

위 내용들을 종합하여 다음과 같은 과정으로 점화식을 도출해봤다. 

기록은 DP 2차원 배열에, R: 0, G: 1. B: 2로 인덱싱 했다. 

 

1. 기저값 설정:

첫 번쨰 집은 이전에 칠한 집이 없으므로 각 색칠 비용 자체가 최소 비용이 됨

$DP[0][0] = cost[0][0]$

$DP[0][1] = cost[0][1]$

$DP[0][1] = cost[0][2]$

 

2. N번째 집을 빨간색으로 칠할 경우

앞집은 초록이나 파랑이어야 하므로 

$DP[i][0]=min(DP[i−1][1],DP[i−1][2])+Cost[i][0]$ 

 

3. N번째 집을 초록색으로 칠할 경우

앞집은 빨강이나 파랑이어야 하므로

$DP[i][0]=min(DP[i−1][0],DP[i−1][2])+Cost[i][1]$ 

4. N번째 집을 파란색으로 칠할 경우

앞집은 빨강이거나 초록이어야 하므로

$DP[i][0]=min(DP[i−1][0],DP[i−1][2])+Cost[i][2]$ 

 

5. 마지막 집까지 진행한 뒤 마지막 집의 최소 비용 후보 중 최소값을 선정하면 된다. 

$Answer=min(DP[N−1][0],DP[N−1][1],DP[N−1][2])$

소스 코드

import kotlin.math.min

fun main() {
    val n = readln().toInt()
    val costs = Array(n) { IntArray(3) }

    for (i in 0 until n) {
        val line = readln().split(" ").map { it.toInt() }
        costs[i][0] = line[0] // 빨강 비용
        costs[i][1] = line[1] // 초록 비용
        costs[i][2] = line[2] // 파랑 비용
    }

    // dp[i][0]: i번째 집까지 칠했고, i번째 집이 빨강일 때의 최소 누적 비용
    val dp = Array(n) { IntArray(3) }

    // 첫 번째 집 초기화
    dp[0][0] = costs[0][0]
    dp[0][1] = costs[0][1]
    dp[0][2] = costs[0][2]

    for (i in 1 until n) {
        // 현재 집(i)을 빨강으로 칠하려면, 이전 집(i-1)은 초록이나 파랑이어야 함
        dp[i][0] = costs[i][0] + min(dp[i-1][1], dp[i-1][2])

        // 현재 집(i)을 초록으로 칠하려면, 이전 집(i-1)은 빨강이나 파랑이어야 함
        dp[i][1] = costs[i][1] + min(dp[i-1][0], dp[i-1][2])

        // 현재 집(i)을 파랑으로 칠하려면, 이전 집(i-1)은 빨강이나 초록이어야 함
        dp[i][2] = costs[i][2] + min(dp[i-1][0], dp[i-1][1])
    }

    // 마지막 집(n-1)에 저장된 값 중 최솟값 출력
    val result = min(dp[n-1][0], min(dp[n-1][1], dp[n-1][2]))
    println(result)
}

 

 

 

시간 복잡도

상수번 연산을 수행하는 반복문이 2개이므로 $O(2N)$, 즉 $O(N)$ 이라고 할 수 있다.