백준 2342번 Dance Dance Revolution - 스위프트(Swift) 풀이

---

 

1. dp(index, left, right) : 현재 두 발의 위치가 left, right일 때 arr[index...]를 모두 밟는 최소 비용
2. dp(index, left, right) = min(왼쪽 발을 움직일 때 비용, 오른쪽 발을 움직일 때 비용)

 

1. dp(index, left, right) : 현재 두 발의 위치가 left, right일 때 arr[index...]를 모두 밟는 최소 비용

 현재의 움직임이 나중에 어떤 영향을 미칠지 예상할 수 없으므로 다이나믹 프로그래밍으로 해결할 수 있다. 현재 두 발의 위치가 left, right일 때 arr[index...]를 모두 밟는 최소 비용을 dp(index, left, right)라고 정의하자. 위치가 5가지이므로 총 5*5*100,000개의 dp 값을 구하게 되고 시간 안에 통과가 가능하다.

 

2. dp(index, left, right) = min(왼쪽 발을 움직일 때 비용, 오른쪽 발을 움직일 때 비용)

 현재 상황에서 할 수 있는 움직임은 두 가지이다. 왼쪽 발을 움직이거나, 오른쪽 발을 움직이는 것. cost(before, after)를 before에 위치한 발을 after로 옮기는 비용이라고 하자. 다음에 밟아야 할 위치가 next라고 하면, 왼쪽 발을 움직일 때의 비용은 cost(left, next) + dp(index+1, next, right)가 되고, 오른쪽 발을 움직일 때의 비용은 cost(right, next) + dp(index+1, left, next)가 된다. 이 중 더 비용이 적게 드는 경우를 선택하면 된다. 기저 사례는 주어진 모든 원소를 다 밟았을 때이므로 index = N일 때이다.

---

import Foundation

let INF = 987654321
var N = 0
var arr = [Int]()
var cache = Array(repeating: Array(repeating: Array(repeating: INF, count: 5), count: 5), count: 100_001)

func calcCost(before: Int, after: Int) -> Int {
    if before == 0 {
        return 2
    } else if before == after {
        return 1
    } else if before + 2 == after || before - 2 == after {
        return 4
    } else {
        return 3
    }
}

// dp(index, left, right): 현재 두 발의 위치가 left, right일 때 arr[index...]를 모두 밟는 비용
func dp(index: Int, left: Int, right: Int) -> Int {
    if index == N { return 0 }
    
    var ret = cache[index][left][right]
    if ret != INF { return ret }
    
    let next = arr[index]
    if right != next {  // 왼쪽 발을 움직임
        ret = min(ret, calcCost(before: left, after: next) + dp(index: index+1, left: next, right: right))
    }
    if left != next {   // 오른쪽 발을 움직임
        ret = min(ret, calcCost(before: right, after: next) + dp(index: index+1, left: left, right: next))
    }
    
    cache[index][left][right] = ret
    
    return ret
}

func solution() {
    arr = readLine()!.split(separator: " ").map{ Int(String($0))! }.dropLast()
    N = arr.count
    
    let result: Int
    
    if N == 0 {
        result = 0
    } else {
        result = 2 + min(dp(index: 1, left: arr[0], right: 0), dp(index: 1, left: 0, right: arr[0]))
    }
    
    print(result)
}

solution()