백준 2156 포도주 시식

포도주 시식 (백준 2156)

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

처음에는 ‘계단 오르기’와 거의 동일한 줄 알고
같은 방식으로 코드를 짠 후,
max(dp) 방식으로 풀었으나
오답이 나왔다

이후, 반례를 찾아보니
포도주를 마실때, ‘몇 칸을 뛰어넘어도 상관 없다’는
부분을 코드에 포함시키지 않았다고 판단하고
max(dp[i],dp[i-1]) 부분을 포함시켜 통과하였다

Code

import sys
inp = sys.stdin.readline

num = int(inp().strip())

val = [0 for _ in range(num+1)]
dp = [0 for _ in range(num+1)]

for i in range(1,num+1):
    val[i] = int(inp().strip())

dp[1] = val[1]

for i in range(2,num+1):
    dp[i] = max(dp[i-3] + val[i-1],dp[i-2]) + val[i]
    dp[i] = max(dp[i],dp[i-1])

print(dp[num])

해결 아이디어

1. dp[i] : i번째 포도주 단계에서 가장 많이 마신 포도주의 양
   
2. dp[i-2] : i-2번재 포도주 단계에서 가장 많이 마신 값
3. dp[i-3] + val[i-1] : 포도주는 3번 연속해서 마실 수 없기에
   3단계 이전의 dp값과 이전 단계에 마셨다는 ‘가정’의 합
   
4. dp[i] = max(dp[i-3] + val[i-1],dp[i-2]) + val[i]
   dp[i]의 점화식으로, ‘계단 오르기’와 동일하게
   i-2번쨰에서 바로 온 경우와, 3번째에서 1번째를 거쳐 온 경우 중 큰 단계와
   현재 값을 더해 결정한다
   
5. dp[i] = max(dp[i],dp[i-1])
   dp[i]가 dp[i-1]보다 작다면 해당 값으로 갱신해준다
   위의 min 값에 포함하는 경우는 +val[i]가 포함되기에 별도로 계산을 해준다
   또한 기본적으로 dp[i-1]은 +val[i]의 비교 점화식에는 들어가지 않기에
   바로 다음인 i+1의 식의 결정에 영향을 끼치지 않는다