BOJ 2449 전구 swift

문제 링크 : https://www.acmicpc.net/problem/2449

 

문제 해설

N개의 전구가 일렬로 배치되어 있고, 각 전구는 1부터 K까지의 색으로 표현됩니다. 한 번에 연속된 같은 색의 전구 그룹을 선택해 다른 색으로 변경할 수 있을 때, 모든 전구를 같은 색으로 만드는 최소 변경 횟수를 구하는 문제입니다.

• 연속된 같은 색 전구를 하나의 그룹으로 압축합니다.
• dp[i][j]를 i번째 그룹부터 j번째 그룹까지 같은 색으로 만드는 최소 횟수로 정의합니다.
• 점화식 : dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + (colors[i] != colors[k + 1] ? 1 : 0)

 

코드

import Foundation

let input = readLine()!.split(separator: " ").map{ Int(String($0))! }
let n = input[0], k = input[1]

let arr = readLine()!.split(separator: " ").map{ Int(String($0))! }

var colors = [Int]()

for i in 0..<n {
    if i == 0 || arr[i] != arr[i - 1] {
        colors.append(arr[i])
    }
}

let m = colors.count

if m == 1 {
    print(0)
} else {
    var dp = [[Int]](repeating: [Int](repeating: Int.max / 2, count: m), count: m)

    for i in 0..<m {
        dp[i][i] = 0
    }

    for length in 2...m {
        for start in 0...(m - length) {
			let end = start + length - 1

            for mid in start..<end {
                let cost = (colors[start] != colors[mid + 1]) ? 1 : 0
                dp[start][end] = min(dp[start][end], dp[start][mid] + dp[mid + 1][end] + cost)
            }
        }
    }

    print(dp[0][m - 1])
}