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

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

알고리즘 분류

• 다이나믹프로그래밍

문제풀이

ex)
d[0]=10
d[1]=10+20=30
d[2]=max(15+10, 15+20)=35

d[3]=max(stairs[3]+d[1], stairs[3]+stairs[2]+d[0])
=max(25+d[1], 25+15+d[0])
d[4]=max(10+d[2], 10+25+d[1])...

첫 번째 경우는 마지막 계단의 전전계단 밟은 경우,
두 번째 경우는 마지막 계단의 전계단과 전전단계까지 최대값을 더해준 경우이다.

• 계단이 3개보다 작을 경우를 고려하지 못하면 인덱스 오류 발생해서 계단을 0으로 초기화 후 진행

소스코드

n=int(input())
stairs=[0]*300
for i in range(n):
  stairs[i]=int(input())

d=[0]*300
d[0]=stairs[0]
d[1]=stairs[0]+stairs[1]
d[2]=max(stairs[2]+stairs[0], stairs[2]+stairs[1])
for i in range(3,n):
  d[i]=max(stairs[i]+d[i-2], stairs[i]+stairs[i-1]+d[i-3])

print(d[n-1])

참고: https://pacific-ocean.tistory.com/149