알고리즘 - Python / 백준 - 2156번 : 포도주 시식

2156번: 포도주 시식 (acmicpc.net)

2156번: 포도주 시식

 

---

풀이

• 포도주가 잔에 담겨 순서대로 놓여 있을 때 , 3잔을 연속으로 마시지 못한다.
• 다음 조건에서 최대한 포도주를 많이 먹으려면 어떻게 해야 하는지 출력하는 문제다.
• 포인트는 3잔 연속 못마시니까 언제 마시는 걸 멈추고 다시 마실까 이다.
• I 번째 포도주를 마시거나 마시지 않거나 , 마신다면 몇 번 연속으로 마시는지 기록하면서 모든 경우를 확인하면 된다.
• 따라서 DP 문제로 접근할 수 있다.
• DP배열은 DP[포도주 번호][0, 1 , 2 = 연속으로 마신 포도주] 로 두었다.
• 배열 업데이트는 DP[I][0] 은 MAX(DP[I-1]) , DP[I][1] = DP[I-1][0] + 포도주[I] , DP[I][2] = DP[I-1][1] + 포도주[I] 로 하면 된다.

 

import sys
n = int(sys.stdin.readline())
c = []
for _ in range(n):
    c.append(int(sys.stdin.readline()))
dp = [[0 for i in range(3)] for i in range(n+1)]
dp[0][1] = c[0];
for i in range(1,len(c)):
    dp[i][0] = max(dp[i-1])
    dp[i][1] = dp[i-1][0] + c[i]
    dp[i][2] = dp[i-1][1] + c[i]
print(max(dp[n-1]))

---