[BOJ] 백준 2579 계단 오르기 Python

2579번: 계단 오르기

문제풀이
이 문제는 DP로 풀 수 있는 문제였다.
DP는 최종 항을 구하기 위해  그전 항들을 완벽히 구할 수 있고 그 항들을 이용해서 현재 항이 깔끔하게 정의될 때 사용할 수 있다.
문제의 그림을 보면 알 수 있듯이 이 전항들이 주어진다.
이 문제의 이름은 계단 오르기지만 사실 DP의 개념으로 문제를 접근해서 해석하면 "계단 내려다보기"이다.
내가 지금 서 있는 지점(항)이 어디로부터 올 수 있는지, 즉 마지막 계단까지의 합을 구할 때 어느 계단으로부터 마지막계단까지 올 수 있는지를 체크하며 문제를 풀어야 한다.
순서
1. 이전 항들을 구한다.(직관적으로 알 수 있다) dp[0],dp[1],dp[2]가 되는 경우의 수가 매우 적기 때문에 직접 구하여 초기 항들을 완성시킨다.
2. 점화식을 구한다.
이 문제에서 N번째 계단에 최대의 값을 가지고 도착하려면
계단 <N-3>까지의 최대값dp[N-3] +
그로부터 두 계단 오른 stairs[N-1] +
그리고 현재의 계단 stairs[N]
VS
계단<N-2>까지의 최대값 dp[N-2] +
현재의 계단 stairs[N] (두 계단을 올랐다. 문제 조건에 의해 계단:<N-1>을 거치지 못한다.)

을 비교했을 때 더 큰 값이 해당 계단까지의 경우의 수들에 대한 최댓값이다.
즉, 점화식은 아래와 같다.

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

 이 문제를 풀면서 유의해야 했던 점은 계단의 개수가 3개보다 작을 때 직접 연산을 해주었으므로 따로 논리 처리를 해주어야 오류가 나지 않는다는 점이었다.

if N >= 2: #이 부분
    dp[1] = stairs[0] + stairs[1]
if N >= 3: #이 부분
    dp[2] = max(stairs[0] + stairs[2], stairs[1] + stairs[2])

 

---

Code

from sys import stdin

input = stdin.readline


def solve():
    N = int(input())
    stairs = []
    for i in range(N):
        stairs.append(int(input()))
    dp = [0] * N
    dp[0] = stairs[0]
    if N >= 2: 
        dp[1] = stairs[0] + stairs[1]
    if N >= 3: 
        dp[2] = max(stairs[0] + stairs[2], stairs[1] + stairs[2])
    for i in range(3, N):
        dp[i] = max(dp[i - 3] + stairs[i - 1] + stairs[i], dp[i - 2] + stairs[i])
    print(dp[-1])


solve()