BOJ(포도주 시식)(2156)

작성일 | In

포도주 시식

  • N개의 포도주 잔이 있을 떄, 최대로 마실 수 있는 포도주의 양을 구해야 한다.
  • 포도주는 연속으로 3잔 이상 마실 수 없다.
  • D[N]: N번째 잔의 포도주를 마셨을 때, 최대로 마실 수 있는 포도주의 양
  • D[N]은 3가지 경우의 수로 나눌 수 있다. 3가지 중 가장 큰 값이 D[N ]이 된다.
    1. N번째 잔을 마시지 않은 경우 D[N-1]
    1. N번째 잔이 연속 1잔째 마신 경우 : D[N-2] + PN번째 잔은 마시지 않아야 한다.
    1. N번째 잔이 연속 2잔째 마신 경우 : D[N-3] + P[N-1] + P[N] (N-2 번째 잔은 마시지 않아야 한다.)
def solve():
    d[1], d[2] = p[1], p[1]+p[2]

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


n = int(input())
d = [0] * (n+2)
p = [0] + [int(input()) for _ in range(n)]+[0]
solve()
print(d[n])

참고자료 codeplus

0%