[백준] 2579 계단 오르기 - Python

2579번: 계단 오르기

POINT

Dynamic Programing (다이나믹 프로그래밍, dp)

피보나치 수열이 대표적인 예시이다. 1. 큰 문제를 작게 나눌 수 있고, 2. 작은 문제에서 구한 결과가 큰 문제에서도 사용되면 Dynamic Programing을 사용한다. 재귀(Top-down), 반복(Bottom-up) 두 가지 방법이 있으며, 시간 복잡도를 고려해서 반복문을 사용한다.

풀이

n = int(input()) # 계단 개수
scores = [0] * (n+1) # 계단 점수
for i in range(1, n+1):
    scores[i] = int(input())

dp = [0] * (n+1)
dp[1] = scores[1] # 계단을 하나 오를 때 최댓값
dp[2] = scores[1] + scores[2] # 계단을 두 개 오를 때 최댓값

for i in range(3, n+1):
    dp[i] = max(dp[i-3] + scores[i-1], dp[i-2]) + scores[i]

print(dp[n])