만득

코딩 공부 정리용

​

© 2021. All rights reserved.

백준 1149 RGB거리

23 Jun 2021

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

각 집마다 색깔을 칠하는 비용이 주어졌을 때 이웃하는 집과의 색과 다르게 색칠하면서 모든 집을 칠하는 비용의 최솟값을 출력하는 문제이다. 코딩 수업을 들은 사람이라면 어디선가 한번쯤은 봤을 문제이다.

var dp = cost[0]
for idx in 1..<n {
    let rcost = min(dp[1], dp[2]) + cost[idx][0]
    let gcost = min(dp[0], dp[2]) + cost[idx][1]
    let bcost = min(dp[0], dp[1]) + cost[idx][2]
    dp = [rcost, gcost, bcost]
}

간단하게 현재 집의 색깔을 R로 할경우 이전 집의 색깔을 G나 B로 했을때의 비용 중 최솟값에 R을 칠할 때의 비용을 더해주면 끝이다. 같은 방식으로 G, B도 업데이트 해주면서 처음부터 끝까지 dp를 업데이트 해주면 된다.

이 때 dp 배열을 [n][3]으로 선언할 필요 없이 바로 직전 값을 활용해서 현재값을 결정하기 때문에 1차원 배열로 선언해주어 메모리를 아끼는 것이 좋다.

let n = Int(readLine()!)!
var cost: [[Int]] = []
for _ in 1...n {
    cost.append(readLine()!.split(separator: " ").map{Int(String($0))!})
}

var dp = cost[0]
for idx in 1..<n {
    let rcost = min(dp[1], dp[2]) + cost[idx][0]
    let gcost = min(dp[0], dp[2]) + cost[idx][1]
    let bcost = min(dp[0], dp[1]) + cost[idx][2]
    dp = [rcost, gcost, bcost]
}
print(dp.min()!)

Related posts