[백준/Python] 2579번 계단 오르기

---

문제

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

---

문제이해

이 문제는 딱 보자마자 다이나믹 프로그래밍을 이용해서 풀어야 하는구나 생각했다.

 

아래의 조건을 살펴보았다.

1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다.
2. 연속된 세 개의 계단을 모두 밟아서는 안 된다.
3. 마지막 도착 계단은 반드시 밟아야 한다.

마지막 3번째 조건은 마지막 계단을 무조건 밟아야 한다는 것이니 마지막 계단부터 계산을 하면 점화식을 세울 수 있을 것이라 생각했다.

---

점화식

• 바로 직전 계단을 밟을 때
  • dp[i] = stairs[i] + stairs[i-1] + dp[i-3]
• 전 전 계단을 밟을 때
  • dp[i] = stairs[i] + dp[i-2]

바로 직전 계단을 밟을 경우,

계단 세 개를 연속으로 밟을 수 없으므로 현재 계단 + 직전 계단 + (i-3)번째 까지의 최댓값 점화식을 세우고

 

전 전 계단을 밟을 경우,

현재 계단 + (i-2)번째 까지의 최댓값 점화식을 세우면 된다.

 

2가지 경우 중 최댓값을 선택하는 점화식을 세우면 이 문제를 풀 수 있다.

---

정답

n = int(input())

dp = [0] * (n+1)

stairs = [0] * (n+1)

for i in range(1,n+1):

    stairs[i] = int(input())

    dp[i] = max(dp[i-2] + stairs[i], dp[i-3] + stairs[i-1] + stairs[i])

print(dp[-1])