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])