[백준/BOJ] - 2156번 python 풀이 - DP

---

Key Point

 

 점화식을 구하기 위해 모든 경우의 수를 따져보면 다음과 같이 3가지 case로 나눠지는 것을 확인 할 수 있다.

노란색 하이라이트 부분이 기준이다.

가장 중요한 점은 dp기준으로 바로 다음 포도주를 먹을 수 있다는 확신이 없다는 점이다.

왜냐하면 dp 기준 바로 이전 포도주를 마셨을 경우 2번 연속 마셨다는 가정이 되는데,

바로 다음 포도주를 마셔버리면 조건에 위배되기 때문이다.

전전전 포도주 dp + 전 포도주 + 현재 포도주

전전 포도주 dp + 현재 포도주

현재 포도주를 마시지 않은 경우

 2579 계단 문제와 다른 점은 마지막 계단을 꼭 밟아야 한다는 조건 때문에 dp를 계산할 때 해당 idx의 계단을 밟는다고 가정하고 값을 구해야한다.

 

반면 해당 문제는 해당 조건이 없으므로 바로 직전 포도주의 dp값을 그대로 넘겨받아도 문제가 없는 것이다.

그렇기에 점화식에 차이가 발생한다.

 

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

2579번: 계단 오르기

https://taewogi.tistory.com/69

[백준/BOJ] - 2579번 python 풀이 - DP

---

 

import sys
input = sys.stdin.readline
n = int(input())
num =[]
dp = [0] * n
for _ in range(n):
    num.append(int(input().rstrip()))
if n <= 2: #case가 2 이하인 경우 num의 합을 출력한다.
    print(sum(num))
    exit(0)
else: #case가 3부터   
    dp[0] = num[0] # 0번째 dp는 그대로 포도주 0을 마심 
    dp[1] = num[0] + num[1] # 1번째 dp는 0, 1번째 포도주를 마심
    # 2번째dp는 현재 포도주를 마시지 x
    # 전 포도주 + 현재 포도주, 전전 포도주 + 현재 포도주 중 가장 큰 값을 저장시킨다.
    dp[2] = max(num[1] + num[2], num[0] + num[2], dp[1]) 

    for i in range(3, n):
    		# 현재 포도주를 마시지 않는 경우
            # 전전전 포도주까지 마셨을 경우의 최댓값(dp) + 전 포도주 + 현재 포도주
            # 전전 포도주를 마셨을 경우의 최댓값(dp) + 현 포도주
            dp[i] = max(dp[i-2] + num[i], dp[i-3] + num[i-1] + num[i], dp[i-1])
#마지막에 최댓값이 저장되므로             
print(dp[-1])