[Algorithm] 백준 - 2156번 포도주 시식 (Swift)

문제 소개

포도주 잔을 2잔 연속해서 마실수있고, 주어진 n개의 포도주의 양중에 최대로 마실수 있는 포도주의 양을 출력하는 문제이다.

 

문제 풀이

와인을 마실경우를 O라고 생각하고 마시지 않을 경우를 X라고 생각하면 앞을 고려하지 않는다면 다음과 같은 경우가 최대가 될 것이다.

하지만 여기서 문제가 있다. 1번 2번 케이스일 경우 앞에서 어떠한 케이스인지 모르기 때문에 함부로 2번 연속해서 마시거나 1번 마실수가 없다. 이미 앞에서 마셨을수도 있기 때문이다.
 
그렇다면 1번 2번 케이스의 X의 앞을 살펴보면 가장 최선의 선택을 했을 경우라는 것을 볼 수 있다.
 
그렇다면 이렇게 생각해보면 어떨까? 내가 생각하기에 다이나믹 프로그래밍은 "내가 계산한 값에 대한 믿음" 이다. 내가 앞에서 계산한 값이 무조건 최선이라고 생각한다면?
 
불확실한 O를 내가한 최선의 선택으로 바꿔버린다면? ...은 아무튼 내가한 최선의 선택이라고 생각한다.

 
그렇다. 나는 아래의 3개의 결과중에 최선의 선택을 해주면 되는 것이다. 최대의 값이니까 세개의 결과중 max를 고르면 될 것이다. w는 입력받은 와인의 배열이라고 생각하면 되고 a[i]는 i번째까지 내가 마실수 있는 최대의 값이다.

 
코드는 아래와 같다.

import Foundation

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

for i in 1...n {
    let wine = Int(readLine()!)!
    w[i] = wine
    
    if i < 3 {
        a[i] = w[i] + w[i-1]
    } else {
        let maxValue = max(a[i-1], a[i-2] + w[i], a[i-3] + w[i-1] + w[i])
        a[i] = maxValue
    }
}

print(a[n])