[백준/2156/파이썬] 포도주 시식

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

2156번: 포도주 시식

Problem

• 1부터 n까지의 번호가 붙어 있는 n개의 포도주 잔이 순서대로 테이블 위에 놓여 있고, 각 포도주 잔에 들어있는 포도주의 양이 주어졌을 때, 효주를 도와 가장 많은 양의 포도주를 마실 수 있도록 하는 프로그램을 작성하시오. 

조건

• 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.
• 연속으로 놓여 있는 3잔을 모두 마실 수는 없다.
• 첫째 줄에 포도주 잔의 개수 n이 주어진다. (1 ≤ n ≤ 10,000) 둘째 줄부터 n+1번째 줄까지 포도주 잔에 들어있는 포도주의 양이 순서대로 주어진다. 포도주의 양은 1,000 이하의 음이 아닌 정수이다.

SOL

계단오르기 문제가 생각난다. 하지만, 이 문제는 마지막 계단을 밟는다는 조건이 없는 문제다.

그렇다면, 경우의 수를 생각해줄 때, n번째 와인을 마실 수 도 있고, 마시지 않을 수 도 있는데, 그 경우에 대해서 생각해보자.

 

우리가 N번째 와인까지의 최댓값을 안다고 가정

• DP[N] = N번째 까지의 최댓값

N번째 와인을 마시는 경우

1. N-3번째 와인까지 최댓값 -> N-1번째 와인 -> N번째 : DP[N-3] + w[N-1]+w[N]
2. N-2번째 와인까지 최댓값 -> N번째 : DP[N-2] + w[N]

N번째 와인을 마시지 않는 경우

• N-1 번째 와인까지의 최댓값을 그대로, 갱신 : DP[N-1]

import sys
input = sys.stdin.readline
N = int(input().rstrip())
w = [0]+[int(input().rstrip()) for _ in range(N)]
DP = [0]*(N+1)

if N==1:
    print(w[1])
    exit(0)
if N==2:
    print(w[1]+w[2])
    exit(0)
else:
    DP[1] = w[1]
    DP[2] = DP[1]+w[2]
    for i in range(3,N+1):
        DP[i] = max(DP[i-3] + w[i-1] +w[i],DP[i-2]+w[i],DP[i-1])
    print(DP[N])