백준 - 계단 오르기 / Silver 3 / 2579번 / Python

문제 📋

백준 - 계단 오르기

풀이 📝

import sys


def solution(n, stairs):
    if n < 3:
        return sum(stairs)
    
    dp = [0] * n
    dp[0] = stairs[0]
    dp[1] = stairs[0] + stairs[1]
    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])

    return dp[n-1]


n = int(sys.stdin.readline())
stairs = [int(sys.stdin.readline()) for _ in range(n)]
print(solution(n, stairs))

1. 문제 정의
   매 계단마다 주어진 점수가 있고 한 계단 혹은 두 계단 씩 오를 때 최대 점수를 구하는 문제이다. 단, 3번 연속 한 계단씩 오르면 안 된다.

2. 시간 복잡도 계산
   계단의 최대 개수는 300개이지만 매 순간마다 해당 계단을 한 계단 뛰어 도착할지 혹은 두 계단 뛰어 도착할지 2가지 경우의 수가 존재하기 때문에 최대 탐색 범위는 2^300으로 매우 크다.

3. 문제 풀이
   따라서 DP로 문제에 접근했고 먼저 dp 배열을 정의했다.

   dp[i] : i 번째 계단까지의 최댓값

   그런 다음 DP 점화식을 구해야 하는데 그 과정이 쉽지 않았다.
   먼저 첫 번째, 두 번째 계단까지는 dp 초기항으로서 쉽게 구할 수 있다.

   i 번째 항을 생각해 보면 i-1 번째 계단을 거쳐서 오는 것과 (한 계단 뛰어오는 것)
   i-2 번째 계단을 거쳐서 오는 것으로(두 계단 뛰어오는 것) 나눠서 생각할 수 있다.

   여기서 주의할 점은 i-1 번째 계단을 거쳐서 온다는 것은 i-2 번째 계단은 안 거친다는 것이다. (3개 연속으로 밟을 수 없기 때문에) 따라서 i-3까지의 최댓값에 i-1과 i 번째 점수를 더해주면 된다.

   반면에 i-2 번째 계단을 거쳐오는 경우는 단순히 i-2까지의 최댓값에 i 번째 점수를 더해주면 된다.

   따라서 점화식은 다음과 같다.

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

4. 예외 사항
   점화식을 보면 i-3번째 항이 존재해야 사용할 수 있기 때문에 dp[3]까지는 초기항들을 이용해 직접 구해야 한다.