문제

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

나의 코드

"""
1. 아이디어
계단오르기와 유사하지만 조건을 따져가면서 신중하게 작성해야 한다.
특히 와인을 마시지 않아도 된다는 점에 주의!

2. 시간복잡도
O(N) 정도? 정확하게 따지면 O(3(n-3))정도 될려나..
"""

from sys import stdin
input = stdin.readline

n = int(input())
wine = [0] * (n+2)
dp = [0] * (n+2)

for i in range(n):
    wine[i] = int(input())

dp[0] = wine[0]
dp[1] = wine[0] + wine[1]
# 와인을 마시지 않아도 되기 때문에 dp[1] 부분을 계단오르기 문제와는 다르게 추가해줘야 함.
dp[2] = max(dp[1], wine[0] + wine[2], wine[1] + wine[2])

for i in range(3, n):
    # 와인을 마시지 않는 경우, 이전 와인을 안먹는 경우, 이전 와인을 먹는 경우
    dp[i] = max(dp[i-1], dp[i-2] + wine[i], dp[i-3] + wine[i-1] + wine[i])

print(max(dp))
    

느낀점

이 문제를 처음 접했을 때 계단오르기 문제하고 비슷해서 쉬운줄 알고 똑같이 작성을 했다가 낭패를 봤다.
https://velog.io/@tyjk8997/%EB%B0%B1%EC%A4%80-DP-%EA%B3%84%EB%8B%A8-%EC%98%A4%EB%A5%B4%EA%B8%B0python

계단오르기 문제하고는 비슷해 보이지만 다른 조건들 때문에 상당히 헷갈렸다. 헷갈린 부분을 정리해보겠다.

• 와인을 안마셔도 되는점(포도주 시식)vs마지막 계단을 꼭 밟아야 하는점(계단 오르기)

1. 첫번째는 와인을 안마셔도 되는 점 때문에 골치가 아팠다. 테스트 케이스 정답은 맞았지만 자꾸 틀리길래 질문게시판을 뒤져본 후 이유를 알게 됐다.

   https://www.acmicpc.net/board/view/60664

   결국 반복문 내에 와인을 마시지 않는 경우 dp[i-1]까지 추가해줘야 맞을 수 있었다. 약간의 조건의 차이지만 조건을 따지지 못해 급하게 코드를 작성한 내 잘못이다.

2. 두번째는 첫번째의 연장선인데 계단오르기 문제에서는 계단을 밟으면 무조건 점수를 더해줘야 했다. 근데 포도주 문제는 포도주를 안마셔도 되기 때문에 dp를 초기화 할때 dp[2] = ~ 부분에서 차이가 났다.

   계단오르기 문제에서는

   dp[2] = max(scores[0] + scores[2], scores[1] + scores[2])

   다음과 같이 3번째 계단을 밟으면 최대의 누적값이 되도록 코드가 작성됐는데

   포도주 문제에서는

   dp[2] = max(dp[1], wine[0] + wine[2], wine[1] + wine[2])

   다음과 같이 dp[1] 즉, 3번째 와인을 안마셔도 되는 부분을 추가해줘야 했다.

이렇게 조건을 잘 따져가면서 신중하게 코드좀 작성하자;;