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

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

2156번: 포도주 시식

 

---

풀이 과정

있는 포도주를 최대로 마시고 싶은데 3잔 연속으로는 마실수 없다는 조건이 걸려있는 문제이다.

 

0번째 연속, 1번째 연속, 2번째 연속으로 마신 경우를 나누어서 고려해 3번째 연속으로 마시는 경우가 나올수 없게 하자.

d[i]를 i번째 까지 마셨을 때의 마신 포도주의 최대 값이라고 하고, p[i]를 i번째 포도주 잔에 들어있는 포도주의 양이라고 하자.

 

0번째 연속으로 마신 경우: d[i-1]

1번째 연속으로 마신 경우: d[i-2] + p[i]

2번째 연속으로 마신 경우: d[i-3] + p[i-1] + p[i]이 성립한다.

 

위의 점화식을 이용해 문제를 해결할 수 있다.

---

소스 코드

import sys

n = int(sys.stdin.readline())
p = []

for _ in range(n):
    p.append(int(sys.stdin.readline()))

d = [p[0], p[0] + p[1] if n > 1 else 0, max(p[0] + p[2], p[1] + p[2], p[0] + p[1]) if n > 2 else 0]

for i in range(3, n):
    d.append(max(d[i-3] + p[i-1] + p[i], d[i-2] + p[i], d[i-1]))

print(d[n-1])