BOJ-1149 RGB거리 Swift

문제

RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.

집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.

• 1번 집의 색은 2번 집의 색과 같지 않아야 한다.
• N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.
• i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.

입력

첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.

내가 푼 풀이

- 집의 갯수가 주어지고 각 줄은 빨강, 초록, 파랑의 색칠비용이 주어진다.

- 규칙에 따르면 결국 인접한 집의 색은 서로 다른색이여야 한다는 것이다.

- 각 줄의 최솟값을 찾아 따라가면, 같은 색을 칠할 경우가 생긴다.

- 집의 갯수가 2개 이상이니,  집을 색칠할 색을 정하고, 그 전에 있는 집의 칠할 수 있는 색의 최솟값을 더하는 식으로 접근했다.

- 위 접근을 점화식으로 표현해본다.

• arr = [R, G, B] , count = 집의 갯수
• dp = Array(repeating: Array(repeating: 0, count: 3), count: count+1)
• dp[n][0] = min(dp[n-1][1], dp[n-1][2]) + arr[0]
• dp[n][1] = min(dp[n-1][0], dp[n-1][2]) + arr[1]
• dp[n][2] = min(dp[n-1][1], dp[n-1][0]) + arr[2]

-> dp[0][0] = 첫번째 집 빨강색비용,  dp[0][1] = 첫번째 집 파랑색비용, dp[0][2] = 첫번째 집 초록비용, 

-> n번째를 빨강으로 칠한다면, n-1번째 집의 파랑,초록 의 최솟값 + n번째 빨강비용

-> 규칙에 따른 모든 집 색칠 비용의 최솟값은 dp[n]의 최솟값이다.

 

 

import Foundation

var count = Int(String(readLine()!))!
var dp = Array(repeating: Array(repeating: 0, count: 3), count: count+1)

for i in 1...count {
    var arr = readLine()!.split(separator: " ").map{ Int(String($0))!}

    if i == 1 {
        dp[1] = [arr[0], arr[1], arr[2]]
        continue
    }
    dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + arr[0]
    dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + arr[1]
    dp[i][2] = min(dp[i-1][1], dp[i-1][0]) + arr[2]
}

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