백준 2579 계단오르기 파이썬 - 다이나믹 프로그래밍(DP), 동적 계획법

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

2579번: 계단 오르기

 

풀이

다이나믹 프로그래밍이라 점화식부터 정하고 풀기 시작했다.

 

 

N번째 계단까지의 최댓값

= max( (N-1)번째 계단까지의 최댓값(단, (N-2)번째는 포함되지 않아야 함) + N번째 계단의 값,

             (N-2)번째 계단까지의 최댓값(단, (N-3)번째 포함 여부는 상관 없음) + N번째 계단의 값)

 

 

직전 값의 전 값도 중요하기 때문에

dp 리스트 요소를 (0, 0) 형태로 잡았다.

 

점화식:

dp[N] = (dp[N-1][1] + N번째 값, max(dp[N-2][0], dp[N-2][1]) + N번째 값)

 

 

 

# 계단 오르기

N = int(input())
stairs = [0]
for i in range(N):
    stairs.append(int(input()))

dp = [(0, 0) for _ in range(N+1)]
dp[1] = (stairs[1], stairs[1])

if N > 1:
    dp[2] = (dp[1][1] + stairs[2], stairs[2])
    for i in range(3, N+1):
        dp[i] = (dp[i-1][1] + stairs[i], max(dp[i-2][0], dp[i-2][1]) + stairs[i])
        
print(max(dp[N]))