** 알고리즘 오답노트 20 (백준 - 2579)

계단 오르기

재귀 함수를 쓰는 문제이다.
하지만 최대 300개의 계단이 있을수 있다고하니, 재귀 함수를 썼을때 너무 깊게 들어가서 시간초과가 난다.
이럴때 동적 계획법을 적용시킨다.

import sys
num = int(sys.stdin.readline())
stair = []
sum_list = [0] * num
for _ in range(num):
  n = int(sys.stdin.readline())
  stair.append(n)

def recursive(x):
  if x == 0:
    sum_list[0] = stair[0]
    return sum_list[0]
  elif x == 1:
    sum_list[1] = stair[0] + stair[1]
    return sum_list[1]
  elif x == 2:
    sum_list[2] = max(stair[0] + stair[2], stair[1] + stair[2])
    return sum_list[2]
  if not sum_list[x]:
    sum_list[x] = max(recursive(x-3) + stair[x-1] + stair[x], recursive(x-2) + stair[x])
  return sum_list[x]
  
print(recursive(num-1))

• github commit

• 문제 링크