[다이나믹 프로그래밍] 백준 실버1 1149번: RGB거리

 

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

1149번: RGB거리

문제 풀이

문제를 정리하면,

• 집의 수 N이 주어진다.
  
• 각 집은 빨강, 초록, 파랑으로 색을 칠해야 하고, 각 집을 칠하는데 집마다 색 별로 비용이 주어진다.
  
• 색을 칠할 땐 인접한 집과 다른 색으로 칠해야 한다. (예를 들어, 2번 집이 빨강이면 1번과 3번 집은 빨강이 아닌 색으로 칠해야 한다.)
  
• 모든 집을 칠하는 비용의 최솟값 출력

이 정도로 문제를 정리해 볼 수 있다.

처음엔, dp 배열을 통해 각 1번 집부터 N 번 집까지 최솟값을 계속 구하면 되는 문제인 줄 알았다.

하지만, 전 집의 색 선택이 다음 집에 영향을 미치기 때문에

i번째 집 까지 비용 최소값 + 조건에 맞는 (i+1)번째 최소 색칠 비용 ==  (i+1)번째 집 까지 비용 최소값

위 조건이 성립하지 않는다.

	빨강	초록	파랑
1	3	5	4
2	100	300	100
3	999	999	1

위 표를 통해 보면,

2번 집까지 최소 비용은 빨강, 파랑으로 칠한 103이다.

하지만, 2번 집을 파랑으로 칠하면, 3번 집을 빨강 또는 초록으로 칠해야 하기 때문에 위 경우의 최솟값인 304를 넘는다.

3번 집을 위해서 2번 집에서 가장 비용이 비싼 초록을 선택해야 한다.

때문에 모든 경우의 수를 종합하여 최솟값을 도출해야 한다.

var dp = Array(repeating: Array(repeating: 0, count: 3), count: n + 1)

위와 같이 dp 배열을 만들어

dp[i][0]은 i 번째 집을 빨강으로 칠했을 때 최솟값

dp[i][1]은 i 번째 집을 초록으로 칠했을 때 최솟값,

dp[i][2]은 i 번째 집을 파랑으로 칠했을 때 최솟값,

위와 같이 나눠 계산한 후에 셋 중 최솟값을 출력하면 된다.

코드

let n = Int(readLine()!)!
var dp = Array(repeating: Array(repeating: 0, count: 3), count: n + 1)
var RGBs: [[Int]] = [[0,0,0]]

for i in 1...n {
    let RGB = readLine()!.split(separator: " ").map { Int($0)! }
    dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + RGB[0]
    dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + RGB[1]
    dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + RGB[2]
}

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