[Swift] 백준 2156 - 포도주 시식

문제 링크

n-2	n-1	n
x	o	o
o	x	o
o	o	x

n번째 포도주를 마실 지 말지 결정할 때 고려해야하는 경우의 수는 다음과 같이 세 가지가 있습니다. 이 중 최대가 되는 경우를 dp[n]에 넣어주면 됩니다.

첫 번째 경우는
dp[n] = dp[n-3] + nArray[n-1] + nArray[n]
두 번째 경우는
dp[n] = dp[n-2] + nArray[n]
세 번째 경우는
dp[n] = dp[n-1]
입니다.

최종 풀이

import Foundation

let n = Int(readLine()!)!
var nArray = Array(repeating: 0, count: 10001)

for i in 1...n {
    nArray[i] = Int(readLine()!)!
}

var dp = Array(repeating: 0, count: n+1)
dp[1] = nArray[1]

if n > 1 {
    dp[2] = nArray[1] + nArray[2]
}

if n > 2 {
    for i in 3...n {
        dp[i] = max(dp[i-2] + nArray[i], dp[i-3] + nArray[i] + nArray[i-1], dp[i-1])
    }
}

print(dp[n])