BOJ/백준-2156-python

문제📖

풀이🙏

• 첫째 줄에 포도주 잔의 개수 n이 주어진다.
• 둘째 줄부터 n+1번째 줄까지 포도주 안에 들어있는 포도주의 양이 순서대로 주어진다.
• 포도주의 양은 1000이하의 음이 아닌 정수이다.
• 포도주 시식의 규칙은 다음과 같은 두 가지이다.
  -> 1. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.
  -> 2. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다.
• 첫째 줄에 최대로 마실 수 있는 포도주의 양을 출력한다.
• DP 알고리즘 문제이다.

코드💻

# boj, 2156 : 포도주 시식, python 
import sys

def DP(wine):
    if n == 1:
        d[0] = wine[0]
    elif n == 2:
        d[0] = wine[0]
        d[1] = wine[0] + wine[1]
    else:
        d[0] = wine[0]
        d[1] = wine[0] + wine[1]
        d[2] = max(d[1], wine[2] + wine[0], wine[2] + wine[1])

    for i in range(3, n):
        d[i] = max(max(wine[i] + wine[i-1] + d[i-3], wine[i] + d[i-2]), d[i-1])
        
    return d[n-1]
    
n = int(sys.stdin.readline())
wine = [int(sys.stdin.readline()) for i in range(n)]
d = [0] * n

print(DP(wine))

결과😎

출처 && 깃허브📝

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