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

 

제일 처음에는 재귀를 이용하여 문제를 풀었다. 

그러나 재귀함수를 이용할 경우 반복되는 연산이 많아 시간초과가 뜬다.

# 재귀호출 ver
import sys
 
num_of_stairs = int(input())
stairs = []
for _ in range(num_of_stairs):
    stairs.append(int(sys.stdin.readline().strip()))
 
# s_n = s_n-1 + a_n or s_n-2 + a_n
def climbing(n, two_step): # two_step은 이전 계단에서 2칸 이동했는지 확인
    if n <= 0:
        return 0
    else:
        if two_step:
            return max((climbing(n-1, False)+stairs[n-1]),(climbing(n-2, True)+stairs[n-1]))
        else:
            return climbing(n-2, True)+stairs[n-1]
 
print(climbing(num_of_stairs, True)) # 초기 two_step 값을 true로 해야 다음 계단을 한칸 혹은 두칸 이동할 수 있다.
 

# 동적프로그래밍 ver
import sys
 
num_of_stairs = int(input())
stairs = []
for _ in range(num_of_stairs):
    stairs.append(int(sys.stdin.readline().strip()))
 
dp = [[0,0] for _ in range(num_of_stairs+1)]
# [0,0]에서 첫번째 수는 계단 한 칸, 두번째 수는 계단 두 칸을 올라갔을 때의 합산 값
 
if num_of_stairs == 1:
    print(stairs[0])
else:
    for i in range(1, num_of_stairs+1):
        dp[i][0] = stairs[i-1] + dp[i-1][1] # 계단을 한 칸만 올라갈 때
        dp[i][1] = stairs[i-1] + max(dp[i-2]) # 계단을 두 칸만 올라갈 때
    print(max(dp[num_of_stairs]))