🟩 [백준] [Python] [DP] 2156번

🗝️ Algorithm/🟩 백준

🟩 [백준] [Python] [DP] 2156번_포도주 시식

Dbswnstjd 2022. 11. 26. 05:17

문제

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

2156번: 포도주 시식

효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규

www.acmicpc.net

풀이

# 백준 2156번 문제 - 포도주 시식
n = int(input())
dp = [0]*10002
grape = [0]*10002
for i in range(1, n+1):
    grape[i] = int(input())

dp[1] = grape[1]
dp[2] = grape[1] + grape[2]

for i in range(3, n+1):
    dp[i] = max(dp[i-1], dp[i-3] + grape[i-1] + grape[i], dp[i-2] + grape[i])
print(dp[n])

DP를 이용해 간단히 풀 수 있었다.