[백준] 2156 포도주 시식

📖 문제

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

💻 내 코드

n=int(input())
mlist=[int(input()) for _ in range(n)]
dp=[0]*n

dp[0]=mlist[0]
if n>1:
    dp[1]=mlist[0]+mlist[1]
if n>2:
    dp[2]=max(dp[1], mlist[0]+mlist[2], mlist[1]+mlist[2])
if n>3:
    for i in range(3,n):
        dp[i]=max(mlist[i]+mlist[i-1]+dp[i-3], mlist[i]+dp[i-2],dp[i-1])

print(max(dp))

💡 풀이

• 현재 인덱스를 i라 했을 때 선택 가능한 경우의 수는

1. mlist[i] 선택, mlist[i-1] 선택, mlist[i-3] 선택
   • mlist[i]+mlist[i-1]+dp[i-3]
2. mlist[i] 선택, mlist[i-2] 선택, mlist[i-3] 선택
   • mlist[i]+dp[i-2]
3. mlist[i] 선택 안함
   - dp[i-1]
   세가지 경우의 수가 있다
   이 중 큰 수를 dp[i]에 저장해주면 됨

• 위 방법은 n이 3보다 커야 적용 가능
• n의 크기가 얼마인지 모르므로 n이 3보다 작을 때의 경우의 수를 나누어 준다