백준 2096 내려가기

출처: www.acmicpc.net/problem/2096

분류: DP

---

접근방식

간단한 DP 문제였습니다.

1, 2, 3 각 열에서 가장 최선인 경우를 계속 선택해나가면 됩니다. 

행마다 갱신하고 나면 그 이전은 생각할 필요가 없으므로 디피는 각 열을 저장할 행 하나만 있으면 됩니다 :)

저는 맨 밑에서부터 올라왔는데 위에서부터 내려가도 상관은 없을듯 하네요!

 

해결방법

let n = Int(readLine()!)!
var num = [[Int]]()

for _ in 0..<n {
    num.append(readLine()!.split(separator: " ").map { Int(String($0))! })
}

var maxDp = num.last!
var minDp = num.last!

for row in num.dropLast().reversed() {
    var maxTmp = [Int](repeating: 0, count: 3)
    var minTmp = [Int](repeating: 0, count: 3)
    maxTmp[0] = row[0] + max(maxDp[0], maxDp[1])
    maxTmp[1] = row[1] + maxDp.max()!
    maxTmp[2] = row[2] + max(maxDp[1], maxDp[2])
    maxDp = maxTmp
    
    minTmp[0] = row[0] + min(minDp[0], minDp[1])
    minTmp[1] = row[1] + minDp.min()!
    minTmp[2] = row[2] + min(minDp[1], minDp[2])
    minDp = minTmp
}

print(maxDp.max()!, minDp.min()!)

 

배운점