[BOJ] 2579 / 계단 오르기 / Python 파이썬

[BOJ] 2579 / 계단 오르기 / Python 파이썬

[BOJ] 2579 / 계단 오르기 / Python 파이썬

https://www.acmicpc.net/submit/2579/29254021

로그인

 

풀이

[BOJ] 2156 / 포도주 시식 과 유사한 문제이다.

 

포도주 시식 문제의 경우 마신다/마시지 않는다의 경우로 선택하지 않는 경우가 있지만,

이 문제의 경우 해당 index 의 계단을 밟지 않는 경우가 없어 고려되지 않는다.

 

그래서 현재 index 의 계단을 밟는 경우는 두가지가 된다.

	i-2	i-1	i
~	O	X	O
~	X	O	O

 

N = int(input())

nums = []

for _ in range(N):
    nums.append(int(input()))
    
dp = [0] * N
dp[0] = nums[0]

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

print(dp[-1])