[백준] 2579 | 계단 오르기 [파이썬/python]

문제

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

계단을 오르면서 얻을 수 있는 점수의 최댓값을 구하는 문제이다.

 

접근

DP를 이용해 문제를 풀었다.

계단마다 점수가 있고, 계단을 오르며 점수를 획득할 수 있다. 계단은 한번에 한 칸 또는 두 칸을 오를 수 있으며, 연속으로 세 칸을 밟을 수는 없다. 마지막 계단은 꼭 밟아야 한다.

마지막 계단에 꼭 도달해야 하므로, '이 계단에 도달하기 전에 어떤 계단을 밟았을까?' 시점에서 문제를 풀면 금방 점화식을 찾을 수 있다.

 

처음에 시작점이 첫 번째 계단인 것으로 잘못 이해해 틀린 답을 한 번 제출했다 ㅎㅎ; 시작점->첫 번째 계단->두 번째 계단->... 이다!

 

코드

import sys
input = sys.stdin.readline

N = int(input())

a = [int(input()) for _ in range(N)]
b = [0] * N
    
if N < 3:
    print(sum(a))
    
else:    
    b[0] = a[0]
    b[1] = b[0] + a[1]
    
    for i in range(2, N):
        b[i] = max(b[i-2] + a[i], b[i-3] + a[i-1] + a[i])
    
    print(b[-1])