[백준] 2156번 포도주 시식

💡문제접근

• 36%에서 넘어가지 못하고 계속 좌절했던 문제였다...
• 단계적으로 예시를 들어가면서 코드를 작성했는데 한참 뒤에 지나서야 문제가 어디에 있었는지 알 수 있었다.

💡코드(메모리 : 30616KB, 시간 : 48ms)

import sys
input = sys.stdin.readline

n = int(input().strip())
dp = [0] * 10001
wine = [0] * 10001
for i in range(1, n+1):
    wine[i] = int(input().strip())

dp[0] = wine[0]
if n >= 4:
    dp[1] = wine[1]
    dp[2] = wine[1] + wine[2]
    # 마실 수 있는 와인의 최대 양
    # ①. 첫 번째 와인 + 두 번째 와인
    # ②. 첫 번째 와인 + 세 번째 와인
    # ③. 두 번째 와인 + 세 번째 와인
    dp[3] = max(wine[1] + wine[2], wine[2] + wine[3], wine[1] + wine[3])
    # 주의할 점
    # 만약 dp[3]이 wine[2] + wine[3] 즉, 두 번째 와인과 세 번째 와인을 마셨을 경우인데 이 경우에는 네 번째 와인을 마시면 안된다.
    # 따라서 for문 안에 dp[i-1]만 있는 것이고 이 뒤에 현재 마실 수 있는 와인의 양 wine[i]을 더해주면 안된다.
    for i in range(4, n+1):
        dp[i] = max(dp[i-2] + wine[i], dp[i-3] + wine[i-1] + wine[i], dp[i-1])
    print(max(dp))
elif n == 3:
    dp[3] = max(wine[1] + wine[2], wine[2] + wine[3], wine[1] + wine[3])
    print(dp[3])
elif n == 2:
    dp[2] = wine[1] + wine[2]
    print(dp[2])
else:
    dp[1] = wine[1]
    print(dp[1])

💡소요시간 : 50m