[백준알고리즘] 2156번: 포도주 시식 -Python

[백준알고리즘] 2156번: 포도주 시식 -Python

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

2156번: 포도주 시식

이전에 풀었던 문제인데 다시 풀어보게 되었다. 동적 계획법 문제이다.

 

존재하는 잔들을 연속된 세 개를 선택하지 못한다. 그러면서 최대의 양을 구해야 하기 때문에 두 선택된 차의 최대 간격은 두 칸이 될 수 있다. 세 칸이 되는 순간부터 A _ _ _ B에서 가운데 한 잔을 더 포함시킬 수 있기 때문이다.

 

또 한 가지 알아야 할 것은 현재의 잔을 포함시킬 때 이전의 잔도 포함되었는지 여부이다. 바로 이전의 잔이 포함되고 현재의 잔이 포함된다면, 두 개의 연속된 잔을 선택한 것이기 때문에 다음 잔은 선택을 못 하기 때문이다. 따라서 이 부분을 해결하기 위해 두 개의 리스트를 만들었다. 하나는 바로 이전의 잔과 현재의 잔을 선택했을 때 마실 수 있는 최대의 양을 나타내고 있고, 또 하나의 리스트는 바로 이전의 잔을 선택하지 않고 현재의 잔을 선택했을 때 마실 수 있는 최대의 양을 나타내고 있다.

간단하게 나타내면 N번째 잔을 선택한다고 했을 때 볼 수 있는 경우의 수는 아래와 같다.

 

N-2	N-1	N
N-3 포함시 최대	N-2 포함시 최대	N-1 포함시 최대
N-3 미포함시 최대	N-2 미포함시 최대	N-1 미포함시 최대

 

여기서 한 가지 더 알아야 할 것은 처음에 두 잔 사이에 떨어질 수 있는 최대의 간격은 2라고 했다. 따라서 N-1 미포함시 최대는 N-2를 포함했을 때의 최대이거나, N-1과 N-2도 포함하지 않고 N-3을 포함했을 때의 최대를 비교하여 그중의 최댓값을 갖고 있게 되는 것이다.

즉 정리하면 아래와 같이 될 수 있다. 여기서 N 선택시 N-2 포함 시 최대와 N-3 포함 시 최대는 각각 N-1번째, N-1과 N-2번째의 잔을 선택하지 않은 경우이다.

 

N-2	N-1	N
N-3 포함시 최대	N-2 포함시 최대	N-1 포함시 최대
N-4 포함시 최대	N-3 포함시 최대	N-2 포함시 최대
N-5 포함시 최대	N-4 포함시 최대	N-3 포함시 최대

 

따라서 이렇게 되면 점화식을 세울 수 있게 되고 그 중에 MAX값을 찾기 위해서 기억해두는 변수를 하나 생성했다.

그리고 최대를 저장하는 리스트에서 각 인덱스에서는 각 인덱스에 위치한 잔을 선택했을 때의 최댓값만 나타낸다.

 

import sys

N = int(sys.stdin.readline())
wine = [int(sys.stdin.readline()) for _ in range(N)]

max_include_before = [wine[0]]
max_exclude_before = [wine[0]]
ans = wine[0]

if N >= 2:
    max_include_before.append(wine[0] + wine[1])
    max_exclude_before.append(wine[1])
    ans = max_include_before[-1]

    def get_max_exclude_before(idx):
        term_one = max(max_include_before[idx-2], max_exclude_before[idx-2])
        term_two = max(max_include_before[idx-3], max_exclude_before[idx-3]) if idx >= 3 else 0

        return max(term_one, term_two)

    for i in range(2, N):
        max_include_before.append(max_exclude_before[i-1] + wine[i])
        max_exclude_before.append(get_max_exclude_before(i) + wine[i])
        ans = max(ans, max_include _before[-1], max_exclude_before[-1])

sys.stdout.write(str(ans))

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다