[Swift] BOJ 2156 포도주 시식

BOJ 2156 포도주 시식

 

접근 방식

 

백준 2579 계단 오르기와 골격은 같고, 마지막 잔을 반드시 마시지 않아도 되는 점만 다름.

계단 오르기에서는 마지막 값을 무조건 선택하지만 포도주는 마지막을 선택하지 않을 수도 있음.

 

예를 들어

[100 100 1 1 100 100]의 결과가 있다고 가정.

계단 오르기 알고리즘을 적용하면 301이 나오나, 포도주 시식 문제에서는 400이 나와야 함.

우선 계단 오르기와 마찬가지로

 

? X O

? X O O

 

로 나누어서 생각했음.

? 자리는 dp 배열에서 O 자리는 리스트에서 뽑기

 

따라서 점화식을 만들 수 있는데, 끝자리를 i라고 가정했을 시

 

1. dp[i-2] + list[i]
2. dp[i-3] + list[i] + list[i-1]

 

이렇게 두 개의 점화식을 만들 수 있음.

 

다만 3연속이 불가하므로 마지막을 선택하지 않는 ? X O O X 경우가 생김.

 

dp 배열은 그 인덱스까지 항상 최선값을 골랐다고 가정함. 위 두 점화식으로 계산한 dp[i]가 dp[i-1]과 같다면, 이번 잔을 선택하지 않고 이전까지의 최선값을 그대로 이어받았다는 뜻임.

 

즉 dp[i] = max(dp[i], dp[i-1])로 이번 잔을 마실지 말지를 결정함. 코드에서 각 i마다 두 점화식의 최댓값을 dp[i]에 넣은 뒤 dp[i-1]과 한 번 더 비교함.

 

코드

 

// https://www.acmicpc.net/problem/2156
import Foundation

struct b2156 {
    
    static func run() {
        // DP를 이용하여 풀어야 합니다.
        let input: Int = Int(readLine()!)!
        var list = [Int]()
        var dp = [Int](repeating: 0, count: input)
        for _ in 0..<input {
            list.append(Int(readLine()!)!)
        }

        if input >= 1 {
            dp[0] = list[0]
        }
        if input >= 2 {
            dp[1] = list[0] + list[1]
        }
        if input >= 3 {
            dp[2] = max(list[0] + list[2], list[1] + list[2])
            dp[2] = max(dp[2], dp[1])
            for i in 3..<list.count {
                dp[i] += max(dp[i-2] + list[i] , dp[i-3] + list[i] + list[i-1])
                dp[i] = max(dp[i], dp[i-1])
            }
            
        }
//        print(dp)
        print(dp.max()!)
    }
}