[Python] 백준 2156번 문제, 포도주 시식

<문제 링크>

 

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

2156번: 포도주 시식

 

---

<풀이>

 

문제에서 원하는 답은 최대로 마실 수 있는 포도주의 양이다. 그런데 주어진 포도주 잔의 개수인 n에 대하여 DP[n]이 최대값이라는게 보장되지 않는다.

따라서 Top-down 방식을 통해 현재 포커싱 중인 index에는 다음을 비교해야 한다.

(1) 기존 최대 포도주 양

(2) 자신의 최대값

(1)은 DP[n-1]이며, (2)는 MAX(비연속, 연속)에서 큰 값에 wine[index]를 더해주면 된다.

 

일단 DP[2]까지는 값이 일정하기 때문에 값을 직접 넣어준다.

N > 2일 경우에, logic() 메소드가 작동한다.

DP[n] 값이 정해져 있지 않다면, (2) 값을 먼저 구한 다음에 MAX((2), (1))을 수행한다.

 

(2)는 위에 설명했듯이 MAX(비연속, 연속)에 wine[index]를 더하는 것이다.

비연속: 기존 최대값에 한 칸 넘어인 wine[index]를 더해야하기 때문에 한 칸 공백을 주기 위해 logic(n-2)

연속: 최대 2잔 연속으로 마실 수 있기 때문에 wine[index] + wine[index - 1]가 추가 되어야 하기 때문에 index-1와 한 칸 거리를 둬야 하기 때문에 logic(n-3) 호출

 

위의 방법으로 (2)를 구한 다음에 마지막으로 (1)과 비교해 큰 값이 DP[n]이 된다.

그럼 기존 최대 포도주 양이 누적되기 때문에 DP[n]을 출력해주면 된다.

 

---

<코드>

sys.setrecursionlimit(10**6): 재귀 함수 깊이를 지정해줘 Recursion Runtime Error를 방지한다.

(이것을 작성하지 않으면 백준에서는 재귀 함수 깊이가 너무 깊어 Recursion Runtime Error가 발생함)

wine: 포도주의 양이 순서대로 주어진다.

(* wine은 0부터 시작, dp는 1부터 시작된다)

---

import sys
sys.setrecursionlimit(10**6) # Recursion Runtime Error 방지 => 재귀 함수 깊이가 깊다면 발생

# dp
def logic(n):
    # 최대값이 정해져 있지 않다면
    if dp[n] is None:
        # 한 칸 건너 뛰고 더한 값과 연속으로 더한 값을 비교한 다음에, 기존 최대 누적값과 비교해 n에 삽입
        dp[n] = max(max(logic(n-2), logic(n-3) + wine[n-2]) + wine[n-1], logic(n-1))

    return dp[n]

if __name__ == "__main__":
    # input
    n = int(sys .stdin.readline())
    wine = [int(sys.stdin.readline()) for _ in range(n)]
    dp = [None for _ in range(n+1)]

    # init
    dp[0] = 0
    dp[1] = wine[0]
    '''
        n이 1이 아닐 경우,
        dp[2]의 최대값은 무조건 1 + 2이다.
    '''
    if n > 1:
        dp[2] = wine[0] + wine[1]

    # result
    print(logic(n))