[Python] 백준(BOJ) 2579번 - 계단 오르기

링크

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

난이도(solved.ac 참고)

실버3

풀이

 

 

세번째 계단까지는 명확하다.

첫 번째 계단: 그냥 한 칸 오르는 게 최대값

두 번째 계단: 두칸을 차례대로 오르는 게 최대값

세 번째 계단: 첫 번째 계단과 두 번째 계단 중 더 큰 값을 갖고 있는 계단에서 올라오는 게 최대값

 

이제 네번째 계단부터는 일반화를 해야한다.

세 개의 계단을 동시에 오를 수 없으므로, 두 번째 계단에서 두 칸을 오르는 것과 세 번째 계단에서 두 칸을 오르고 첫 번째 계단에 도달한 뒤 거기에서 한 칸을 오르는 것 중에서 더 큰 값이 최대값이 된다.

 

이를 도식화한 것이 아래의 코드이다.

for i in range(3, n):
    dp[i] = max(dp[i-2], dp[i-3]+a[i-1])+a[i]