계단 오르기

2579번: 계단 오르기

 

나의 풀이

import sys
input = sys.stdin.readline

ct = int(input())
up_list = [int(input()) for _ in range(ct)]

dp = [0]*ct
if ct==1:
    print(up_list[0])
elif ct==2:
    print(up_list[0]+up_list[1])
else:
    dp[0] = up_list[0]
    dp[1] = up_list[0]+up_list[1]
    dp[2] = max(up_list[0] + up_list[2], up_list[1] + up_list[2])
    for i in range(3, ct):
        dp[i] = max(dp[i - 2] + up_list[i], dp[i - 3] + up_list[i - 1] + up_list[i])

    # 최종적으로 마지막 계단에서의 최대 점수 출력
    print(dp[ct - 1])

 

 

시간 복잡도

dp = [0]*ct : 계단 크기만큼 dp리스트 생성 ( 선형 시간 복잡도 )
for i in range(3, ct) : 크기만큼 순회하며 dp초기화 ( 선형 시간 복잡도 )
해당 알고리즘 최종 시간 복잡도는 선형 시간 복잡도 (O(n))