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

문제 설명

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

2579번: 계단 오르기

 

---

문제 풀이

점화식 구하기

2번째 전 계단을 밟는 경우

   => D[i - 2] + floor[i]

1번째 전 계단을 밟는 경우 (연속된 세 계단을 밟으면 안 되기 때문에 3번째 계단을 밟고 1번째 전 계단으로 올라와야 한다)

   => D[i - 3] + floor[i - 1] + floor[i]

 

이 두 경우 중 최댓값이 D[i]이 된다!

점화식 : D[i] = max(D[i - 2] + floor[i], D[i - 3] + floor[i - 1] + floor[i])

 

n = int(input())
floor = [0] * 301
d = [0] * 301

for f in range(n):
    floor[f + 1] = int(input())

d[1] = floor[1]
d[2] = floor[1] + floor[2]
d[3] = max(floor[1] + floor[3], floor[2] + floor[3])

for i in range(4, n + 1):
    d[i] = max(d[i - 2] + floor[i], d[i - 3] + floor[i - 1] + floor[i])

print(d[n])