BOJ-2156 포도주 시식

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

문제 소개

n개의 숫자가 주어졌을 때 연속으로 3개의 숫자를 선택하지 않는 조건 하에서 선택한 숫자의 합의 최댓값을 구한다.

문제 풀이

DP로 풀이하였다. dp라는 리스트를 하나 두고 풀어도 되지만, 여기서는 prev, cur라는 두 리스트를 선언하고 값을 갱신시켜가며 풀이하였다.

포도주 잔이 하나씩 추가되는 것을 단계의 진행으로 보았을 때, 다음 단계는 이전 단계의 값을 이용하여 구할 수 있다.

prev는 이전 단계의 값을 의미하며, cur는 추가된 잔을 통해 업데이트되는 값을 의미한다.

prev와 cur의 인덱스 0, 1, 2의 값은 각각 단계에 도달했을 때 포도주를 몇잔째 마셨는지를 나타낸다.

예를 들어, cur[1]은 현재 단계를 포도주 1잔째 마시는 것으로 도달한 경우 마신 포도주의 최대 누적값이다.

반복문 내에서 i번째 cur을 갱신하는 동작은 3개가 이루어진다.

1. cur[0] : prev의 값 중 최대값.
2. cur[1] : prev[0] + arr[i]이다. 1잔째 마시는 경우 이전 단계는 0잔째 마신 경우이다.
3. cur[2] : prev[1] + arr[i]이다. 2잔째 마시는 경우 이전 단계는 1잔째 마신 경우이다.

매 반복문마다 prev의 값을 cur의 값으로 지정해준다.

결과는 max(cur)이 된다.

코드

import sys
input = lambda: sys.stdin.readline().rstrip()

n = int(input())
arr = [int(input()) for _ in range(n)]

prev, cur = [0] * 3, [0] * 3        # 리스트 초기화

for i in range(n):
    cur[0] = max(prev[0], prev[1], prev[2])
    cur[1] = prev[0] + arr[i]
    cur[2] = prev[1] + arr[i]

    prev = cur.copy()

print(max(cur))