[Swift] 백준 17404 - RGB 거리 2

문제 바로가기

RGB거리 문제를 풀었다면,, 도움이 많이 되는 문제이다..!

RGB 거리 풀이에
for 문을 넣어서 첫 번째 집의 값을 각각 R,G,B로 지정한 경우만 고려해주면 되기 때문이다!

그러니까..
먼저 첫번째 집의 값을 R로 지정한 경우

dp[1][0] = R
dp[1][1] = MAX
dp[1][2] = MAX

로 지정하여 첫번째 집의 값이 R이 아닌 경우 최소값이 절대 나올 수 없게 한다.
그 이후는 RGB거리 풀이와 동일하게 하여 최소값을 구하고

첫번째 집의 값이 R이므로 마지막 집의 값은 R이 될 수 없기 때문에
dp[N][0]을 제외한
dp[N][1]과 dp[N][2] 중 최소값을 구한다.

이 과정을 첫번째 집의 값이 G인경우, B인경우도 반복하여
최종적으로 구해진 최소값을 출력하면 된다

(집을 칠하는 비용은 최대 1000이고 집의 수는 2에서 1000사이의 수 이므로 가능한 최대 값 MAX = 1000x1000 + 1이다)

최종 풀이

import Foundation

let N = Int(readLine()!)!
let max = 1000*1000 + 1

var nArray = Array(repeating: Array(repeating: 0, count: 3), count: N+1)
var dp = Array(repeating: Array(repeating: 0,count: 3), count: N+1)
var result = max

for i in 1...N {
    let a = readLine()!.split(separator: " ").map{Int(String($0))!}
    nArray[i] = a
}

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

}

print(result)

• for 문을 줄이기 위해서
  • j가 0인 경우 a가 1, b가 2
  • j가 1인 경우 a가 2, b가 0
  • j가 2인 경우 a가 0, b가 1로 되도록
    j에 1과 2를 더한 값을 3으로 나눈 나머지 값을 사용하였다.