백준 2156번(포도주 시식) 파이썬

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

2156번: 포도주 시식

오랜만에 dp문제를 풀어보았다. dp 문제는 점화식 설정이 매우 중요하다.

문제를 보고 경우의 수를 그려가며 어떤 차례에서 경우의 수가 반복 된다면 그때부터 점화식의 설정해서 풀면 된다.

그러면 까다로운 조건이 있지 않는 한 금방 풀릴것이다.

아래는 코드와 주석으로 달아놓은 풀이이다.

점화식만 설정하면 풀리는 문제들이라 설명이 크게 길지가 않다.

꼭 본인이 경우의 수를 그려가며 풀어보길 권한다.

import sys
input = sys.stdin.readline

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

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

dp[1] = wine[1]
dp[2] = wine[1]+wine[2]
dp[3] = max(dp[2],wine[1]+wine[3],wine[2]+wine[3]) #3가지의 경우의 수를 먼저 대입해준다.

for i in range(4,n+1):
    dp[i] = max(dp[i-1],dp[i-2]+wine[i],dp[i-3]+wine[i-1]+wine[i]) # 각각의 경우의 수를 비교해가며 dp리스트를 채워준다.

print(dp[n]) # 해당 dp 출력