[백준/파이썬] 2156번

📍백준 2156 문제

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

코드

import sys
input = sys.stdin.readline

n = int(input())
grape = [0]*10000
dp = [0]*10000
for i in range(n):
    grape[i] = int(input())
dp[0] = grape[0]
dp[1] = grape[0] + grape[1]
dp[2] = max(dp[1], grape[0]+grape[2], grape[1]+grape[2])

for i in range(3, n):
    dp[i] = max(grape[i]+dp[i-2], grape[i]+grape[i-1]+dp[i-3], dp[i-1])
print(max(dp))

풀이

계단 문제와 유사하다.
현재 값에서 가질 수 있는 경우의 수

• 현재 위치를 건너 뛰는 경우
• 현재 위치 건너 뛰지 않음 + 이전 값을 건너 뛴 경우
• 현재 위치 건너 뛰지 않음 + 이전 값을 건너 뛰지 않은 경우