BAEKJOON #2579 계단 오르기

이 문제의 저작권은 BAEKJOON에 있습니다.

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

 

풀이

1. 비어있는 dp, 계단 리스트 생성
2. 3번째 계단까지 미리 계산하고 dp에 삽입
3. 4번째 계단부터 마지막 계단까지 문제에서 주어진 규칙에 따른 최댓값을 구한다.

# 계단 오르기
# https://www.acmicpc.net/problem/2579

N = int(input())

# 계단이 최대 300개 까지 있음
dp = [0] * 301
# stairs리스트 미리 생성해서 인덱스 에러 해결
stairs = [0] * 301

for s in range(N):
    stairs[s] = int(input())

dp[0] = stairs[0]
dp[1] = stairs[0] + stairs[1]
dp[2] = max(stairs[1]+stairs[2], stairs[0]+stairs[2])

for i in range(3, N):
    # 마지막 계단 -1 번째 계단을 밟는 것, 안밟는 것 중
    # 최댓값을 구한다.
    dp[i] = max(dp[i-3] + stairs[i-1] + stairs[i], dp[i-2]+stairs[i])
print(dp[N-1])