[Swift] 백준 1149 - RGB거리

문제 링크

만약 첫번째 집이

• R을 칠한다면
  • 두 번째 집은 G 또는 B
• G를 칠한다면
  • 두 번째 집은 R 또는 B
• B를 칠한다면
  • 두 번째 집은 G 또는 R
    만 칠할 수 있다.

이때 모든 집을 칠한 최솟값을 구해야하는데
첫번째 집의 RGB 중 최솟값으로 선택한다고 해도 전체를 칠한 최종 결과 값 최솟값이라고 확신할 수는 없다.

예를 들어
[[51, 37, 63],
[89, 29, 100],
[83, 58, 11]]

다음과 같이 RGB값을 가지는 세 집이 있을 때
첫번째 집의 RGB값으로 최소 값인 37을 택한다면
37 -> 89 -> 58 => 184 이지만
51을 택한다면
51 -> 29 -> 11 => 91 이므로
최솟값이 아니더라도 최종값은 최솟값일 수 있다.

따라서 R, G, B 세 경우를 모두 다루고 최종값 중 최솟값을 출력해주는게 좋다.

풀이 코드

import Foundation

let N = Int(readLine()!)!
var nums : [[Int]] = [[]]
var dp = Array(repeating: Array(repeating: 0, count: 3), count : 1001)
for i in 0..<N {
    let a = readLine()!.split(separator:" ").map { Int(String($0))! }
   nums.append(a)
}

for i in 1...N {
    for j in 0..2 {
        let a = (j+1)%3
        let b = (j+2)%3
        
        dp[i][j] = min(dp[i-1][a],dp[i-1][b]) + nums[i][j]
    }
}

print(min(dp[N][0],dp[N][1],dp[N][2]))