[ BOJ 2156 ] 포도주 시식(Python)

문제

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

포도주를 최대한 많이 마시는 문제다. 부럽다🙃
이때 3잔 연속으로 마실 수 없다는 점을 고려해야 한다.

문제 풀이

포도주의 양을 기록해줄 dist 리스트를 만들어주었다.

dist[i]에는 i번째 위치에 왔을 때, 가장 많이 마실 수 있는 포도주의 양이 기록된다.

말로 풀어서 설명하는 것보다 그림으로 보는게 훨씬 이해가 빠를 것 같아서 만들어보았다.

i번째 인덱스에 있을 때 세가지 상황을 고려해야 한다.
1. wine[i] + wine[i-1] + dist[i-3]
2. wine[i] + dist[i-2]
3. dist[i-1]

🔥 3칸의 법칙을 지키면서 최대한 많은 칸의 포도주를 마신다고 반드시 최적의 해를 얻을 수 있는 것이 아니다.
예를 들자면 다음과 같은 경우이다.

4번째 칸에 있는 포도주를 마시면, 연속 3칸이 되어버리므로 6번째 칸의 포도주를 마실 수 없게 되었다.

따라서 dist[i]에 넣어줄 최댓값을 비교할 때, dist[i-1]도 반드시 고려해줘야 한다.

dist[i] = max(wines[i] + wines[i-1] + dist[i-3], 
              wines[i] + dist[i-2],
              dist[i-1])

코드

import sys
input = sys.stdin.readline
INF = sys.maxsize

n = int(input().rstrip())
wines = [0] * (n+1)
dist = [0] * (n+1)

for i in range(1,n+1):
    wines[i] = int(input().rstrip())

if n==1:
    print(wines[1])
    sys.exit(0)
elif n==2:
    print(wines[1]+wines[2])
    sys.exit(0)
else:
    dist[1] = wines[1]
    dist[2] = wines[1] + wines[2]
    dist[3] = max(wines[1] + wines[3], wines[2] + wines[3], dist[2])

    for i in range(4,n+1):
        # dist[i] = wines[i] + max(wines[i-1] + dist[i-3], 
        #                         wines[i-2] + dist[i-3])
        dist[i] = max(wines[i] + wines[i-1] + dist[i-3], 
                      wines[i] + dist[i-2],
                      dist[i-1])

    print(dist[n])