[백준] 2156 포도주 시식 (Python 파이썬)

www.acmicpc.net/problem/2156

2156번: 포도주 시식

문제 설명

포도주가 ( a, b, c, d, e, f ) 식으로 일렬로 나열되어 있다. a, b, c, d...는 포도주의 용량을 뜻한다.

연속으로 3잔 이상을 마실 수 없을 때, 최대로 마실 수 있는 포도주의 용량을 구하면 된다.

---

풀이 과정

6잔의 포도주 ( 6, 10, 13, 9, 8, 1 ) 가 있다고 생각해보자.

마지막 포도주를 마실지 말지를 결정하는 상황이라고 할 때,

내가 9와 8을 이미 마셨다면 1은 마실 수 없으며,

13과 9을 마신경우와 13과 8을 마신 경우에는 1을 마실 수 있다.

 

이 경우 중에서, 가장 많이 마실 수 있는 상황을 고르면 되는 것이다.

 

즉, 현재 포도주를 마실 지 말지를 결정 할 때는

① 현재 포도주와 이전 포도주를 마시고 전전 포두주는 마시지 않는다. ( wine[i]+wine[i-1]+d[i-3] )

② 현재 포도주와 전전 포도주를 마시고 이전 포도주는 마시지 않는다. ( wine[i]+d[i-2] )

③ 현재 포도주를 마시지 않는다. ( d[i-1] )

 

이 세 가지 경우로 나눌 수 있다.

이 때, 3번케이스의 경우 d[i-2]+wine[i-1] 로 표기하지 않은 이유는

d[i-1]에 해당 케이스를 포함한 최댓값이 저장되어 있기 때문이다.

 

포도잔이 3잔 이하인 경우에는 인덱스에러를 방지하기 위해 예외처리를 먼저 해주면 코드가 완성된다.

n = int(input())

wine = []

for i in range(n):
    wine.append(int(input()))

d = [0]*n

d[0] = wine[0]
if n > 1:
    d[1] = wine[0]+wine[1]

if n > 2:
    d[2] = max(wine[2]+wine[1], wine[2]+wine[0], d[1])

for i in range(3, n):
    d[i] = max(d[i-1], d[i-3]+wine[i-1]+wine[i], d[i-2]+wine[i])

print(d[n-1])

 

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !