백준: 2156 포도주 시식

문제

2156번: 포도주 시식

 

문제 풀이

 포도주 마셨을 때 가장 많이 마시는 경우를 찾는 문제이다. 문제의 제한사항으로 연속해서 3잔 이상의 포도주를 마실 수 없다. 처음부터 세잔의 와인을 마실 경우 마실 수 있는 포도주는 다음과 같다.

 

• OXO : 중간 와인을 마시지 않는 경우
• OOX : 세 번째 와인을 마시지 않는 경우
• XOO : 첫 번째 와인을 마시지 않는 경우

 즉, 이전 와인과 현재 와인을 마시는 경우와 전전의 와인과 현재 와인을 마시는 경우, 현재 와인을 마시지 않는 경우로 나뉘어 진다.

 

코드

from sys import stdin

if __name__ == '__main__':
    n = int(stdin.readline())
    memo = [0] * (n + 1)
    wine = [0] + [int(stdin.readline()) for _ in range(n)]
    if n > 1:
        memo[1], memo[2] = wine[1], wine[1] + wine[2]
    else:
        memo[n] = wine[n]
        
    for i in range(3, n + 1):
        memo[i] =\
            max(memo[i - 1],
                memo[i - 3] + wine[i - 1] + wine[i],
                memo[i - 2] + wine[i])
    print(memo[n])