2579 계단 오르기

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

✔ 유형 : DP

✔ 문제 풀이: 계단을 오를 때, 앞에서부터 계산해서 최대값을 구하는 것이 아닌, 최종 도착지를 정해놓고 그전 계단을 밟았을때 밟지 않았을 때 중의 최댓값을 구해나가 memorization을 한다.

 

 

⬇️ 코드

import sys
input = sys.stdin.readline

N = int(input())
arr = list()
for _ in range(N):
    arr.append(int(input()))
DP = [0] * (N+1)


DP[1] = arr[0]
if N >=2:
    DP[2] = DP[1] + arr[1]

for i in range(3, N+1):
    DP[i] = max(DP[i-2] + arr[i-1], DP[i-3]+ arr[i-1]+ arr[i-2])
    
print(DP[N])