[백준] 2156번 포도주 시식 (by Python)

문제

짜고 보니 몇 줄 안됐지만 하루종일 머리 싸매다가 다른 분의 해설을 보고 나서야 해답을 찾은 문제.

 

풀이

import sys
input = sys.stdin.readline

n = int(input())
arr = []
ans = [0 for _ in range(n)]
for _ in range(n):
    arr.append(int(input()))

ans[0] = arr[0]
if n > 1:
    ans[1] = arr[0] + arr[1]
if n > 2:
    ans[2] = max(arr[0] + arr[1], arr[1] + arr[2], arr[0] + arr[2])

for i in range(3, n):
    ans[i] = max(ans[i - 1], ans[i - 2] + arr[i], ans[i - 3] + arr[i - 1] + arr[i])

print(ans[n - 1])

 

ans 리스트에서 ans[i] 값은 i번째 잔까지 있다고 했을 때 먹을 수 있는 최댓값이다. 세 번째 값까지 초기화했다면 다음 ans[i]들은 모두 3가지 경우의 범위 내에 속하게 된다.

 

① 이전 값과 연속으로 더해질 때 (ans[i - 3] + arr[i - 1] + arr[i])

② 이전 값은 뛰어넘고 더해질 때 (ans[i - 2] + arr[i])

③ 더해지지 않을 때 (ans[i - 1])

 

이 세 가지 중에서 가장 큰 값을 대입해주면 가장 최선의 ans[i]를 찾을 수 있다.