[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])
Author And Source
이 문제에 관하여([Swift] 백준 2156 - 포도주 시식), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@sun02/백준-2156-Swift-포도주-시식저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)