[Swift] 백준_RGB거리(1149)

문제

 

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

1149번: RGB거리

 

 

풀이

 

처음으로 직접 점화식을 찾고 한 번에 맞췄다. 

 

테이블을 정의하는게 중요한 것 같은데, 나는 문제에서 필요한 것들을 토대로 접근했다. 

우선, 문제에서 요구하는 답인 집을 칠하는 비용의 최소값 정보를 가지고 있어야한다고 생각했다. 또한, 비용을 구할땐 이웃한 집의 색이 달라야한다고 생각했기때문에 색에 대한 정보도 필요하다고 생각해서 result배열을 2차원으로 잡았다.

 

그래서 result[k][0] 은 k개의 집을 칠하는데 마지막 집이 빨간색인 경우라고 정했다. 마찬가지로,

result[k][1]은 k개의 집을 칠하는데 마지막 집이 초록색인 경우, 그리고

result[k][2]는 k개의 집을 칠하는데 마지막 집이 파란색인 경우라고 생각했다.

 

이렇게 정하게 되면 뒤의 값에 따라 이전의 집이 어떤 색이어야 하는지 정할 수 있기때문에 배열을 채워나갈 수 있다. 

따라서, 점화식은 아래와 같이 구해진다.

 

result[k][0] = min(result[k-1][1], result[k-1][2]) + cost[k][0]

 

마지막 집을 0, 1, 2중 어떤 것을 하냐에 따라 점화식에 들어갈 값이 달라진다. 이렇게 구한 세 개의 값 중 최소값을 출력하면 된다.

import Foundation

let n = Int(readLine()!)!
var cost: [[Int]] = [[0]]
for _ in 0..<n {
    cost.append(readLine()!.split(separator: " ").map { Int(String($0))! })
}
var result = Array(repeating: Array(repeating: 0, count: 3), count: n + 1)
result[1][0] = cost[1][0]
result[1][1] = cost[1][1]
result[1][2] = cost[1][2]
for i in 2...n {
    result[i][0] = min(result[i - 1][1], result[i - 1][2]) + cost[i][0]
    result[i][1] = min(result[i - 1][2], result[i - 1][0]) + cost[i][1]
    result[i][2] = min(result[i - 1][0], result[i - 1][1]) + cost[i][2]
}
print(result[n].min()!)

 

 

_____________________________________________________________________________________________________

 

 

뿌듯하긴한데 운이 좋았던 것 같다.