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

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

2156번: 포도주 시식

 

 

Python

import sys
input = sys.stdin.readline
n = int(input())
arr = [ int(input()) for _ in range(n) ]

if n<3:
    print(sum(arr))
    sys.exit(0)

# i번째에 까지 누적했을 때 합
dp = [] # [i-3번째, i-2번째, i-1번째]
dp.append([0, 0, arr[0]])
dp.append([0, arr[1], arr[1]+arr[0]])
dp.append([arr[2], arr[2]+arr[0], arr[2]+arr[1]])

for i in range(3,n):
    # i-3번째
    # 한 칸 이상 건너뛰었기에
    # i-4, i-5, i-6 어디서 오든 상관없다
    three = arr[i] + max(dp[i-3])
    # i-2번째
    # 한 칸 이상 건너뛰었기에
    # i-2번째 값은 i-3번째든, i-4번째에서 오든 상관 없다.
    two = arr[i] + max(dp[i-2])
    # i-1번째
    # 연속 세 개 제한 규칙으로
    # i-1번째 값은 (i-1)-1번째만 제외하고 계산해야 한다
    one = arr[i] + max(dp[i-1][0], dp[i-1][1])
    
    dp.append([three, two, one])


# 마지막 원소를 꼭 포함하지 않았을 때도 최대값이 나올 수 있기에
print(max(max(dp[n-2]), max(dp[n-1])))
#print(dp)

 

 

 

풀이

아래 문제와 유사해보이지만, 2칸 이상 패스하는 것을 고려해야 하는 이유 

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

2579번: 계단 오르기

 

아래와 같은 예시의 경우, 

답은 200이 아닌 101이 나오게 된다.

 

4

100

1

1

100

 

위의 예시를 조금 수정하여,

낮아진 수 사이에 높은 수를 하나 끼워 넣으면,

한 칸씩만 점프하여 와인을 마실 수 있기 때문에

1칸 점프 뿐만 아니라 2칸 점프 또한 고려해야하는 문제였다.

5

100

1

100

1

100