백준 - Dance Dance Revolution (2342)

let input = readLine()!.split(separator: " ").map { Int(String($0))! }
let mp = [
          [0, 2, 2, 2, 2],
          [2, 1, 3, 4, 3],
          [2, 3, 1, 3, 4],
          [2, 4, 3, 1, 3],
          [2, 3, 4, 3, 1]
         ]
var dp = Array(repeating: Array(repeating: Array(repeating: 1000000, count: 5), count: 5), count: input.count)
dp[0][0][0] = 0

for count in 1..<input.count {
    let num = input[count - 1]
    
    for i in 0..<5 { // 오른발 옮기는 경우
        if num == i {
            continue
        }
        for j in 0..<5 {
            dp[count][i][num] = min(dp[count - 1][i][j] + mp[j][num], dp[count][i][num])
        }
    }
    for i in 0..<5 { // 왼발 옮기는 경우
        if num == i {
            continue
        }
        for j in 0..<5 {
            dp[count][num][i] = min(dp[count - 1][j][i] + mp[j][num], dp[count][num][i])
        }
    }
}

var answer = Int.max
dp[input.count - 1].forEach {
    answer = min(answer, $0.min()!)
}

print(answer)

수열의 최대 길이가 10만이므로 모든 경우의 수를 점화식으로 표현해서 구한다.

점화식 dp[N][L][R]은 N개의 수열을 수행한 후 왼발의 위치가 L, 오른발의 위치가 R일 때 최소 누적 힘이다.

이 점화식을 사용해서 직전 (N-1) 수열을 수행한 후 왼발과 오른발을 각각 한 번씩 움직이는 모든 경우의 수를 구해서 최소 힘을 구한다.