[백준]2156번 포도주 시식 - DP

 

n = int(input())

grape = [0] * (n+2)
dp = [0] * (n+2)
for i in range(n):
    grape[i]= int(input())

dp[0] = grape[0]
dp[1] = grape[0]+grape[1]
dp[2] = max(grape[0]+grape[1], grape[0]+grape[2], grape[1]+grape[2]) # 포도주가 3개일 경우에서 최대 값.

for i in range(3, n):
    dp[i] = max(dp[i-2]+grape[i], dp[i-3]+grape[i-1]+grape[i], dp[i-1]) # 포도주를 마시지 않는 경우 까지 고려.

print(max(dp))

 

코드 설명

먼저 인덱스의 에러를 피하기 위해 n+2 길이 만큼의 grape와 dp 리스트를 선언한다.

그 후 dp 의 초기값을 정해준다. 포도주가 1잔인 경우 1번째, 2잔인 경우 1,2 번째 3잔인 경우에는 1, 2 / 1, 3 / 2, 3 번째 잔을 고르는 값중 제일 큰 값을 선택한다.

반복문을 진행하면서 3가지의 경우를 고려한다. 저장된 값중 가장 큰 값을 출력한다.

 

Point : 3잔 까지의 초기식을 세우고 그 이상의 경우에는 점화식을 세워서 해결한다.

3가지의 경우의 수가 생길 수 있다.

case 1 : i-2번째 포도주 누적 + 현재 포도주 -> dp[i-2]+grape[i]

case 2 : i-1번째 포도주 누적 + 현재 포도주 -> dp[i-1]+grape[i] -> 그러나 이 경우 3잔 연속마시는 경우가 생길 수 있다.

따라서 dp[i-3]번째의 값 + grape[i-1] + grape[i] 의 식으로 바꾸어 연속마시는 경우를 없애준다.

case 3 : 이번 포도주를 마시지 않고 넘어가는 경우 -> dp[i-1] (직전 값을 그대로 이용)