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

문제 보러 가기~!

아이디어 🌊

내가 전에 풀었던 DP들과는 다른 유형(?)인 것 같아서,,, 생각하다가 모르겠어서 친구에게 힌트를 얻었다.. 이런 점화식은 도대체 어떻게 생각해내는지 신기하다!! ㅠㅠ

코드 👩‍💻

n = int(input())
wines = []
for _ in range(n):
    wines.append(int(input()))
wines.insert(0,0)
drunk_wine = list([0]*(n+1) for _ in range(3))
# print(drunk_wine)

for i in range(1, n+1):
    drunk_wine[0][i] = max(drunk_wine[0][i-1], drunk_wine[1][i-1], drunk_wine[2][i-1])
    drunk_wine[1][i] = drunk_wine[0][i-1] + wines[i]
    drunk_wine[2][i] = drunk_wine[1][i-1] + wines[i]

print(max(drunk_wine[0][n], drunk_wine[1][n], drunk_wine[2][n]))