[동적계획법/DP] 백준 2579 계단 오르기 - Python

 

[ Contents ]

 

 

1. 문제 (링크 참조)

2579번: 계단 오르기

 

 

 

2. 문제 풀이

1. 한 번에 1계단 또는 2계단씩 오를 수 있다.
2. 연속된 3계단을 밟을 수 없다.
3. 마지막 계단은 반드시 밟아야 한다.

 

 계단마다 획득 가능한 점수가 있고, 위 규칙을 따라 최대 점수를 획득해야 합니다.

 

2022.02.12 - [Algorithm] - [Algorithm] 메모해두고 불러와서 사용하는 동적 프로그래밍(DP)

[Algorithm] 메모해두고 불러와서 사용하는 동적 프로그래밍(DP)

 한 계단 혹은 두 계단씩 오를 수 있으니, 두 경우를 고려해야 합니다.

 

 

 

3. 코드

import sys
input = sys.stdin.readline

n = int(input())
stairs = []
for _ in range(n):
    stairs.append(int(input()))

if n == 1:
    print(stairs[0])
elif n == 2:
    print(stairs[0]+stairs[1])
else:
    cache = [stairs[0], stairs[0]+stairs[1], max(stairs[0]+stairs[2], stairs[1]+stairs[2])]
    for i in range(3, n):
    	#끝에서 2번째인 계단을 밟는 경우와 끝에서 1, 3번째인 계단을 밟는 경우를 비교
        cache.append(max(cache[i-2]+stairs[i], cache[i-3]+stairs[i-1]+stairs[i]))
    print(cache[n-1])

 연속된 3계단을 밟을 수 없으므로, 마지막 계단을 밟는 경우의 수는 2가지입니다.

 1) 끝에서 2번째인 계단을 밟는 경우

 2) 끝에서 1, 3번째인 계단을 밟는 경우

 

위 두 가지 경우를 비교해서, 더 높은 점수를 cache에 저장합니다.