파이썬으로 풀어보는 백준 2579번: 계단 오르기

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

2579번: 계단 오르기

 

내 풀이:

n = int(input())
 
if n == 1:
    a = int(input())
    print(a)
    exit()
 
if n == 2:
    a = int(input())
    b = int(input())
    print(a+b)
    exit()
 
score = [0] * n
for _ in range(n):
    score[_] = int(input())
 
last1 = [0] * n
last2 = [0] * n
last1[0] = score[0]
last1[1] = score[0] + score[1]
last2[1] = score[1]
for i in range(2, n):
    last1[i] = last2[i-1] + score[i]
    last2[i] = max(last1[i-2] + score[i], last2[i-2] + score[i])
 
print(max(last1[n-1], last2[n-1]))

Python3, 64ms

동적 계획법을 이용한 문제. n개의 계단(0부터 n-1)에 대한 점수를 score 리스트에 저장하고 i번 째 계단을 오를 때 마지막으로 한 계단을 오른 경우 중 최댓값을 last1[i]에, 마지막으로 두 계단을 오른 경우 중 최댓값을 last2[i]에 저장하여 문제에 해당하는 규칙성을 적용하여 마지막 계단까지 도달했을 때 최댓값을 출력한다.