[Baekjoon][Python] 2579번 계단 오르기

2579번 계단 오르기

문제

풀이

다이나믹 프로그래밍(DP)를 이용하여 해결하는 문제이다.

반복문을 돌며, 이전 값들을 이용하여, 현재의 값을 구하면 된다.

문제의 조건을 보면,
1. 계단을 한 계단 또는 두 계단 씩 오를 수 있으므로 3계단 이상은 못 오르게 된다.
2. 그리고 3개의 계단이 연속되면 안된다
3. 마지막 계단을 꼭 밟아야 한다

이 3가지 조건들을 만족하려면 아래와 같이 생각하면 된다.

(현재 위치에서 2단계 아래 값과 현재 위치의 점수를 더한 값)과 (현재 위치에서 3단계 아래 값 + 현재 위치에서 1단계 아래 값 + 현재 위치의 점수를 더한 값) 중 큰 값을 택하면 된다.
마지막 값 위치에서 어떤 값을 택해야 할지 생각을 해보면 조금 더 쉽게 이해할 수 있을 것이다.

import sys

def operateDP(n):
    scores = [0]
    dp = [0]
    for _ in range(N):
        scores.append(int(input()))

    dp.append(scores[1])

    if N > 1:
        dp.append(dp[1] + scores[2])

    for i in range(3, N + 1):
        dp.append(max(dp[i - 2] + scores[i], dp[i - 3] + scores[i - 1] + scores[i]))
    return dp[n]

input = sys.stdin.readline

N = int(input())

print(operateDP(N))

결론

처음에는 조금 복잡하게 생각하여 코드가 매우 더럽게 나왔었다. 다른 풀이들을 참고하여 생각을 다듬으니 코드 정리가 깔끔하게 되었다. DP의 경우 개념은 거의 유사하기 때문에 한 두번만 제대로 해놓으면 다름 문제도 잘 해결할 수 있을 것 같다.