[백준] (Swift) 1149번 - RGB거리 (dp 의 가장 대표적인 유형, 마지막 수에 따라 달라지는 경우의 수)

문제링크

https://www.acmicpc.net/problem/1149

1149번: RGB거리

 

풀이 IDEA

우선, 문제를 읽어보면 조건이 세개 나 달려있지만, 다 같은 말이다. 그저 집의 색상은 앞뒤 집과 겹치지 않아야 한다는 하나의 조건일 뿐인 것이다. 1번집이 빨간색이면, 2번집은 파랑이나 초록이면 되고, 50번째 집이 빨강이라면, 49번집과 51번집은 빨강이 아니면 된다.

나는 이문제를 보고 바로 이 문제(click!!)를 풀었던 경험을 생각했다. 마지막에 어떤 수를 배치하느냐에 따라 현재의 색상이 달라지기 때문에 경우의 수를 나눠서 생각해야한다는 것이다. 우리는 집마다 다른 rgb 색상 가격도 입력받아야하고, dp 배열도 작성해야하기 때문에 헷갈리지 않도록 표로 그려서 문제를 풀었다.

우선 맨 처음에 n 에 대한 상수를 입력받는다.

let n = Int(readLine()!)!

 

그 다음 RGB 가격에 대한 입력을 3차원 배열로 입력받았다. 아래 써있듯이 R색상은 인덱스 0으로 지칭할 것이고, G는 1, B는 2로 지칭할 것이다. 

var rgbPrice = Array(repeating:[0,0,0], count: n+1) //RGB => 012 순서

for i in 1..<n+1 {  // rgbPrice[집번호][012순서대로 가격]
    rgbPrice[i] = readLine()!.split(separator: " ").map {Int(String($0))!}
}

그리고 우리는 dp 배열을 생성할 것이다. dp 배열은 n x 3 의 크기로 만들 것이다. 여기서 n 은 처음에 입력받은 집의 개수이다. 그럼 우리는 dp[집번호][R, G, B] 이러한 배열을 가질 수 있다.

var dp = Array(repeating: Array(repeating: 0, count: 3), count: n+1) //dp[집번호][색상]

 

이제 입력을 모두 받았으니, dp 점화식을 찾아보자. 조건으로 주어진 것처럼, 1번집이 만약 R 색상이라면, 2번집은 G나 B색상으로 칠해져야하고, 2번 집 색상이 G로 칠해졌다면, 3번 집은 R이나 B로 칠해져야 한다. 이를 표로 나타내보자.

위와 같은 표를 얻을 수 있다. 모든 경우의 수를 구하고, dp[마지막집]의 R,G,B 값에서 최소값을 찾으면 정답이 될 것이다. 우리는 최소값을 구하면 되기 때문에, 이전에 무슨색상이 칠해져 있는지만 살펴보고, 지금 칠할 수 있는 색상 중 최소가격을 갖는 색상을 찾아 더해주면 되는 것이다. 

그래서 내가 지금 손에 들고 있는 색상이 R 이라면, 이전 집에 G가 칠해졌을때와 B가 칠해져있을때를 비교하여 최솟값을 가져오고, 이어서 지금 내가 손에 들고 있는 색상 R을 칠해주면 된다. 이를 점화식으로 표현하면 생각보다 간단하다.

어디서 많이 봤던 규칙이다!! 우리가 이렇게 마지막에 오는 수나 색상, 조건을 고려하여 문제를 풀때 항상 이러한 규칙의 점화식이 나온다. dp는 많이 연습할 수록 많이 풀수록 규칙이 더 잘보일 것 같다.

위에서 설명한 것들을 코드로 구현하면 아래와 같다.

 

전체 소스코드 - 맞았습니다!

let n = Int(readLine()!)!
var rgbPrice = Array(repeating:[0,0,0], count: n+1) //RGB => 012 순서
var dp = Array(repeating: Array(repeating: 0, count: 3), count: n+1) //dp[집번호][색상]
for i in 1..<n+1 {  // rgbPrice[집번호][012순서대로 가격]
    rgbPrice[i] = readLine()!.split(separator: " ").map {Int(String($0))!}
}


for i in 1..<n+1 {
    dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + rgbPrice[i][0]
    dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + rgbPrice[i][1]
    dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + rgbPrice[i][2]
}

print(dp[n].min()!)