Python으로 푸는 백준 2579. 계단 오르기

백준 2579. 계단 오르기

계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다.

계단에는 일정한 점수가 쓰여있으며 계단을 밟으면 그 계단에 쓰여있는 점수를 얻게 된다.

계단에 오르는 규칙을 지키며 계단의 꼭대기에 올랐을 때, 얻을 수 있는 총 점수 최댓값을 구하는 프로그램을 작성하시오.

백준에서 푼 문제 리스트 보기

백준에서 문제 보기

Github에서 코드 보기

문제 조건

계단을 오르는 규칙은 다음과 같다.

1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.

2. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.(0층)

3. 마지막 도착 계단은 반드시 밟아야 한다.

문제 풀이

이 문제의 핵심은 계단을 오르는 규칙을 잘 지키며 계단 꼭대기에 올라갔을 때 얻을 수 있는 최댓값을 구하는 것이다. 이 문제는 DP(복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법)로 문제를 해결할 수 있지만 내가 DP로 문제들을 많이 풀어보지 않았기 때문에 이 문제에 어떻게 접근하고 어떤 값을 Memoization 해두는 것이 좋을지에 대해 감이 오지 않았다. 완전 탐색하는 방법으로도 문제는 풀 수 있겠지만 주어진 계단의 수가 커질 수록 시간 초과가 나올 수 밖에 없다.

이 문제는 연속된 세 개의 계단을 모두 밟아선 안된다는 조건 때문에 멘붕이 오기가 쉽다. 직전과 그 전전칸이 무엇인지에 대한 여부에 따라서 다음 칸을 밟아도 되는지 안되는지에 대한 여부가 결정된다는 것이므로! 사실 백준 1563. 개근상 문제처럼 연속해서 계단을 밟았는지에 대한 여부를 기록하면서 문제를 풀어나갈수도 있다.하지만 이 문제는 약간의 규칙만 발견하면 연속해서 계단을 밟았는지에 대한 정보를 기록할 필요 없이  더욱 DP스럽게(?) 문제를 풀어나갈 수 있다.

앞으로 어떤 계산을 밟을 것인가 vs 어떤 계단을 밟고 올라왔을까?

계단을 올라가는 것만 생각하지 말고, 이미 올라간 상태에서 이전에 내가 어떤 계단을 밟고 올라올지를 생각하는 방식으로 사고를 전환해보자.

앞으로 어떤 계단을 밟을 것인가 vs 어떤 계단을 밟고 올라왔을까?

생각해보자. 내가 현재 n번째 계단에 있다. 내가 오르기 전에 밟고 있던 계단의 경우의 수는 총 2가지이다. 두가지의 경우의 수 중에서 더 큰 값이 답이 된다.

첫 째, 한칸 전(n-1) 계단을 밟고 올라온 경우이며 이럴 땐 세번 연속 계단을 오를 순 없으므로 그 이전 계단은 그 전전인 (n-3)번째 계단이 된다.

두번 째, 두칸 전(n-2) 계단을 밟고 올라온 경우이다.

직전 칸에서 올라온 경우 vs 전전 칸에서 올라온 경우

중복된 계산을 피하기 위해서 내가 기록해 두어야 하는 값은 n칸 까지 올라왔을 때 얻을 수 있는 최댓값이며, 위의 그림을 모두 이해하였다면 코드를 짜는건 어렵지 않다.

파이썬 코드

import sys
input = sys.stdin.readline
 
 
def solve(stair, n):
    dp = []
    dp.append(stair[0])
    for i in range(1, 3):
        if i == 1:
            dp.append(max(dp[i-1] + stair[i], stair[i]))
            continue
        dp.append(max(dp[i-2] + stair[i], stair[i-1] + stair[i]))
 
    for i in range(3, n):
        # i번째 계단으로 올라오기 위해 max(직전 계단을 밟은 경우, 직전 계단을 밟지 않은 경우)
        dp.append(max(stair[i] + stair[i-1] + dp[i-3], stair[i] + dp[i-2]))
    # print(dp)
    print(dp[-1])
 
 
if __name__ == "__main__":
    stair = []
    n = int(input().strip())
    for i in range(n):
        stair.append(int(input().strip()))
 
    solve(stair, n)