[백준] 2156번 문제 (포도주 시식) 파이썬(Python) 풀이

t = int(input())
wines = [0] + [int(input()) for _ in range(t)]
dp = [0] + [wines[1]]
 
if t > 1:
    dp.append(wines[1] + wines[2])
 
for i in range(3, t + 1):
    case1 = dp[i - 1]                           # 이번 포도주를 안 먹는 경우
    case2 = wines[i] + dp[i - 2]                # 이번 포도주를 먹고 저번 포도주를 안 먹는 경우
    case3 = wines[i] + wines[i - 1] + dp[i - 3] # 이번 포도주를 먹고 저번 포도주를 먹는 경우
    dp.append(max(case1, case2, case3))
 
print(dp[t])

해당 포도주일때 경우의 수가 세 가지로 나뉜다.

 

1. 이번 포도주를 안 먹는 경우

2. 이번 포도주를 먹고 저번 포도주를 안 먹는 경우

3. 이번 포도주를 먹고 저번 포도주를 먹는 경우 

 

이 3가지 경우에서 max값을 구해 dp에 append 하면서 답을 구한다.

dp 문제이긴 하지만 약간 그리디 문제 같기도 하다.