[백준] 2579 계단 오르기 파이썬 풀이 (동적 계획법)

문제

계단은 한번에 한 계단 or 두 계단씩 오를 수 있다.

연속 세개를 밟으면 안된다.

마지막 도착 계단은 반드시 밟아야한다.

이때 얻을 수 있는 점수의 최댓값을 구해라

 

문제 풀이

• 계단이 1개일때는 1개만 밟을 수 있다
• 계단이 두개일때는 두개 다 밟을 수 있다.
• 계단 세개일때는 마지막 계단은 꼭 밟아야하니, 첫번째 계단과 두번째 계단 중에서 점수가 높은 것을 밟을 수 있다.
• 계단이 네개 이상일때는 그 전 계단을 밟은 게 점수가 큰지, 전 계단을 안밟은게 점수가 큰지 확인한다.

코드

 

import sys
 
step_total = int(input())
steps = []
for _ in range(step_total):
    steps.append(int(sys.stdin.readline().rstrip()))
 
# dp
dp = [0]*step_total
dp[0] = steps[0]
# 계단이 2개 이상일때
if step_total >= 2:
    dp[1] = steps[0] + steps[1]
# 계단이 3개 이상일때
if step_total >= 3:
    dp[2] = max(steps[0], steps[1]) + steps[2]
# 계단이 4개 이상일때
for idx in range(3, step_total):
    dp[idx] = max(dp[idx-2], steps[idx-1]+dp[idx-3]) + steps[idx]
 
print(dp[step_total-1])

---