[알고리즘][Python] 백준 2579 계단 오르기 문제 풀이

문제 출처 : www.acmicpc.net/problem/2579

2579번: 계단 오르기

---

문제 해석 : 계단에 적힌 수들을 합하면서 올라간다. 이때 한번에 한 개씩 3개 이상의 계단을 오르지 못하고 2계단을 한번에 이동할 수 있다. 수의 최대값을 구하는 문제이다.

 

문제 풀이 :  전형적인 DP 문제로 점화식을 도출 할 수 있다. 한번에 3개의 계단을 연속적으로 이동하지 못하기 때문에 

1. 이전계단과 자신의 계단 + 3칸 전 최대값

2. 두개 이전의 계단의 최대값 + 자신의 계단

중 가장 큰 값을 구하면 된다. 이때 이전의 계산은 dp 테이블로 따로 연산을 진행한다. 

---

풀이 코드

N = int(input())

arr = [0 for i in range(N+3)]
dp = [0 for i in range(N+3)]

for i in range(N):
    arr[i] = int(input())

dp[0] = arr[0]
dp[1] = arr[0] + arr[1]
dp[2] = max(arr[1] + arr[2], arr[0] + arr[2])
for i in range(3, N):
    dp[i] = max(dp[i-3] + arr[i-1] + arr[i], dp[i-2] + arr[i])

print(dp[N-1])

---

author : donghak park
contact : donghark03@naver.com

## 문제의 저작권은 백준 알고리즘 사이트에 있습니다. 혹시 문제가 되는 부분이 있으면 연락 바랍니다.