[DP] 2156번 포도주시식

"이것이 코딩테스트다(나동빈 저)"에서 나온 문제에 대한 코드를 다루고 있습니다.
문제에 대한 구체적인 설명과 조건 등은 책을 참고해주시기 바랍니다.

소요시간: 

1. 문제 설명

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

2156번: 포도주 시식

2. 접근 방식

- 최대로 마실 수 있는 포도주의 양을 출력, n = 4
- 3까지는 입력해준다.
- 만약 n일 때 마실 수 있는 경우의 수를 구하면
    - n을 안 마시는 경우: dp[n-1]
    - n을 마시는 경우 처음일 때: n + dp[n-2]
    - n을 마시는 경우 두번째일 때: n+ n-1 +dp[n-3]

+ 해당 문제의 경우 1, 2일 때 별도의 조건을 설정해줘야 하고, 포도주를 마시지 않고 넘기는 경우도 생각해야 한다.

3. 코드

import sys
input = sys.stdin.readline

n = int(input())
ls = [0] + [int(input()) for _ in range(n)] + [0]
dp = [0]*(n+2)
dp[1] = ls[1]
dp[2] = dp[1]+ls[2]
for i in range(3, n+1):
    dp[i] = max(dp[i-3]+ls[i]+ls[i-1], dp[i-2]+ls[i], dp[i-1])
print(dp[n])

4. 코멘트

- 초기에 점화식을 잘 성정했었는데 중간에 1과 2일 때, 조건을 별도로 넣는 과정에서 흐름을 고려하지 못해서 꽤 오랫동안 헤맸다...

- 내 코드를 기준으로 코드를 변경하고 추가해야 후에도 코드를 이해하거나, 수정하기 수월하다는 것을 기억해야 한다.

- 해당 문제는 점화식을 잘 설정했지만, 이상한 부분에서 시간을 더 많이 쓴 것 같다. 아직 내 코드에 대한 확신이 부족한 것 같다.