[Swift] BOJ 2158 포도주 시식

BOJ 2158 포도주 시식

 

✅ 비슷한 유형을 일전에 풀어본 기억이 있어서 금방 풀겠다 했었는데, 무지 오래 걸렸음.

백준 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]의 값이 선택되지 않은 케이스임. (list[i] > 0) 그 케이스의 경우에는 마지막을 선택하지 않음.

 

다시 말해서 이번에 선택하지 않았으면 이전(i-1)까지의 최선값이 현재(i)와 같은 값이 된다.

즉 max(dp[i], dp[i-1])을 통해서 이번에 선택할지 말지에 대한 결정을 할 수 있다.

따라서 마지막에 dp[i] 의 값과 dp[i-1]값을 비교해서 더 큰 값을 dp[i]에 넣어준다. 

 

🟠 코드

// 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()!)
    }
}