백준 2156번: 포도주 시식 python

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

문제 접근

• 포도주는 연속으로 3잔을 마실 수 없다는 제한이 있다.

• 마실 수 있는 경우는 다음과 같다:

  1. 이번 잔을 마시지 않는다.
  2. 이번 잔과 바로 전 잔을 마시고, 그 전 잔은 마시지 않는다.
  3. 이번 잔과 그 전 전 잔을 마시고, 바로 전 잔은 마시지 않는다.

• 따라서, i번째 포도주까지의 최대 양을 dp[i]라고 할 때 다음과 같이 점화식을 세울 수 있다.

해답 및 풀이

import sys

# 입력
input = sys.stdin.readline
n = int(input())  # 포도주 잔의 개수
wine = [0]  # 인덱스를 1부터 시작하기 위해 0을 앞에 추가
for _ in range(n):
    wine.append(int(input()))

# dp 배열 초기화
dp = [0] * (n + 1)

# 초기값 설정
dp[1] = wine[1]
if n >= 2:
    dp[2] = wine[1] + wine[2]

# 점화식 적용
for i in range(3, n + 1):
    dp[i] = max(
        dp[i - 1],                            # 현재 잔을 마시지 않음
        dp[i - 2] + wine[i],                 # 전 잔 마시지 않고 현재 잔 마심
        dp[i - 3] + wine[i - 1] + wine[i]    # 전 전 잔 마시고 전 + 현재 잔 마심
    )

# 결과 출력
print(dp[n])