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])