2156번 - 포도주 시식

연속으로 3개를 고르면 안되고 마실수 있는 최대 포도주를 구하는 문제입니다.
전에 풀었던 계단 문제와 비슷한 감이 없잖아 있는데 조금 더 복잡합니다.

분석

본 문제는 세 가지 경우로 나눠서 풀 수 있습니다.

1. i번째 잔을 아예 고르지 않거나
2. i-3번째 잔 -> i-1번째 잔 -> i번째 잔을 통해 올라오거나
3. i-2번째 잔 -> i번째 잔을 통해 올라오는 경우

이렇게 세 가지로 정리할 수 있겠습니다.
자세한 풀이가 필요한 분들은

https://velog.io/@ghost_dog/%EA%B3%B5%EB%B6%80-2024.01.24-%EC%98%A4%EB%8A%98%EC%9D%98-%EC%BD%94%EB%94%A9%EA%B3%B5%EB%B6%80

를 참조하시면 원활하게 이해 가능하실 겁니다.

계단 오르기와 다른 점은 계단은 무조건 밟아야 하지만 이 포도주는 안마셔도 상관이 없으므로 안마시는 경우에는 이전까지의 최대 dp값 (dp[i-1])을 해당 dp에 넣어주면 되겠습니다.

코딩

n = int(input())
lst = []
for _ in range(n):
    a = int(input())
    lst.append(a)

리스트를 받아줍니다.

dp = [0]*n
if n>=1:
    dp[0] = lst[0]
if n>=2:
    dp[1] = lst[0]+lst[1]
if n>=3:
    dp[2] = max(lst[0]+lst[2],lst[1]+lst[2],dp[1])

점화식에서 dp[i-3]이 최소 참조 인덱스이므로 3까지 기본값을 설정해줍니다. 다만, 주의할 점은 lst의 값이 2 이하일 경우 list out of range exception이 발생할 수 있으므로 1과 2값을 직접 지정해주도록 합시다.

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

3부터는 아까 세운 점화식 중 최댓값을 dp[i]에 대입시켜주면 됩니다.

print(max(dp))

마지막으로 dp의 최댓값을 출력하면

정상적으로 해를 도출할 수 있습니다.