브론즈3

문제 2579

해당 문제 링크

정답

## 계단 오르기
import sys
sys.setrecursionlimit(10**6)

input=sys.stdin.readline
n=int(input())

arr=[int(input()) for _ in range(n)]

dp=[]

if n==1:
    print(arr[0])
elif n==2:
    print(arr[0]+arr[1])
else:
    dp.append(arr[0])
    dp.append(arr[0]+arr[1])
    dp.append(max(arr[0]+arr[2], arr[1]+arr[2]))
    for i in range(3, n):
        dp.append(max(dp[i-2]+arr[i], dp[i-3]+arr[i]+arr[i-1]))

    print(dp[-1])

풀이

dp[i] 는 i번째 계단까지 밟았다고 가정했을 때 가장 큰 경우의 값을 저장하는 배열이다.

마지막 도착 계단(end)은 반드시 밟아야 하기 때문에 마지막 계단을 밟는 다는 조건 하에 2가지의 경우가 존재한다.
1. 밟은 계단이 end-1일 경우, end-2 계단은 밟으면 안된다. => 연속된 세 개의 계단을 모두 밟으면 안되기 때문이다.
2. 밟은 계단이 end-2일 경우, 그 이전 계단은 신경 안써도 된다.
이 두 가지를 고려한 식은
dp.append(max(dp[i-2]+arr[i], dp[i-3]+arr[i]+arr[i-1])) 이다.