백준 2156 포도주 시식

haruponea·2021년 4월 4일
0

BOJ

목록 보기
36/41

문제 링크https://www.acmicpc.net/problem/2156

풀이
포도주를 3번 연속해서 마실 수 없다는 것은 0번 연속, 1번 연속, 2번 연속까지 마실 수 있다는 뜻입니다. dp[i]를 i개가 주어졌을 때 마실 수 있는 포도주의 최댓값이라고 정했습니다.

  1. 0번 연속
    i번째 잔을 0번 연속 먹었다는 것은 안먹었다는 것을 의미합니다. i-1번째 잔을 먹든 안먹든 상관없이 i번째만 안먹으면 되기 때문에 **dp[i] = dp[i-1]**이 됩니다.
  2. 1번 연속
    i번째잔을 마시고 i-1번째 잔을 안먹는 경우입니다. i-2번째 잔은 먹든 안먹든 상관없기 때문에 **dp[i] = dp[i-2] + wine[i]**가 됩니다.
  3. 2번 연속 i, i-1번째 잔을 먹는 경우입니다. i, i-1번째 잔을 먹으므로 i-2번째 잔은 먹으면 안됩니다. i-3번째 잔은 먹든 안먹든 상관없습니다. 따라서 **dp[i] = dp[i-3] + wine[i-1] + wine[i]**가 됩니다.

위 점화식 중에서 최댓값을 찾으면 되므로 최종적인 점화식은 다음과 같습니다.

dp[i] = max(dp[i-1], dp[i-2] + wine[i], dp[i-3] + wine[i-1] + wine[i])

python

import sys
input = sys.stdin.readline
n = int(input())
wine = [0]
for _ in range(n):
    wine.append(int(input()))
dp = [0]*(n*3)
dp[1] = wine[1]
dp[2] = wine[1]+wine[2]
dp[3] = max(wine[1]+wine[2], wine[1]+wine[3], wine[2]+wine[3])
for i in range(4, n + 1):
    dp[i] = max(dp[i-1], dp[i-2]+ wine[i], dp[i-3] + wine[i]+wine[i-1])
print(dp[n])

0개의 댓글