코딩 테스트/백준

[Python] 백준 2579 계단 오르기

위시리 2025. 3. 11. 11:13

 

문제 분석

  • 계단은 한 번에 한 계단 or 두 계산씩 오를 수 있다.
  • 연속된 세 개의 계단을 모두 밟으면 x 
  • 시작점은 계단에 포함 x
  • 마지막 도착 계단을 밟아야 한다.
  • 각 계단의 점수가 주어질 때 계산 꼭대기에 도달할 때 최대 점수

  • 계산의 개수는 300이하의 자연수
  • 계산에 쓰여 있는 점수는 10,000이하의 자연수

 

풀이

  • 마지막 계단은 무조건 밟아야 한다.
  • 마지막 계단 -1 까지의 최대값
  • 마지막 계단 -2 까지의 최대값
  • 마지막 계단부터 거꾸로 계산?
  • 완탐 시 300 계단 : 1 - 2 - 4 - 8 - ... → 2^300-1 : 완탐 불가
  1. i번째 계단을 밟을 수 있는 경우의 수는?
    • 계단의 규칙에 따르면 각 계단에 도달할 때 얻을 수 있는 최대 점수는 전의 계단과 관련이 있다.
    • i번째 계단을 밟을 때 얻을 수 있는 최대 점수는
    • i번째 계단을 오르기 직전 계단에서 얻을 수 있는 최대 점수와 관련이 있다. → DP
    • i번째 도달할 수 있는 방법은?
      1. (i-2)번째 계단을 밟은 후, 2칸을 올라 i번째 계단에 도달
      2. (i-1)번째 계단을 밟은 후, 1칸을 올라 i번째 계단에 도달
        • but 이러면 i-1번째 계단을 한 칸 올라 밟았는지, 두 칸 올라 밟았는지 알 수 없다.
        • & 연속해서 세번 한 칸 오르는 경우를 막기 위해 다음과 같이 생각할 수 있다.
        • i-3번째 계단을 밟은 후, 2칸 올라 i-1번째 계단에 도달한다. 그 후 1칸에 올라 I번째 계단에 도달한다.
        • 이렇게 하면 i-3번째 계단을 어떻게 올라왔던 규칙에 맞게 계단을 오를 수 있다.
  2. DP 설계하기

(1) 관계식 구하기

DP는 앞에 계산해 놓은 값을 재활용해 뒤의 문제의 답을 구하는 방식이다.
→ 앞의 값들을 활용해 뒤의 값을 어떻게 구할 것인가

dp[ i ] = i번째 계단에서 획득할 수 있는 최대 값
arr[ i ] : i 번째 계단에서 얻을 수 있는 점수

  1. i-2번째 계단을 밟은 후, 2칸을 올라 i 번째 계단에 도달
    • i-2번째 계단에서 얻은 최대 점수 + i번째 계단의 점수가 최댓값
    • dp[i-2] + arr[ i ]
  2. i-3번째 계단을 밟은 후, 2칸을 올라 i-1번째 계단에 도달하고, 그 후 1칸을 올라 i 번째 계단 도달
    • i-3번째 계단에서 얻은 최대 점수 + (i-1)번째 계단의 점수 +i번째 계단의 점수가 최댓값
    • dp[i-3] + arr[i-1] + arr[ i ]

dp[ i ]는 1번과 2번에서 얻을 수 있는 점수 중 최댓값이다.
즉, dp[i] = max(dp[i-2], dp[i-3] + arr[i-1]) + arr[i]

만약 dp[i-1]을 고려하면, dp[i] = dp[i-1] + arr[i]를 계산해야 한다.
그러나 dp[i-1]은 이미 dp[i-2] + arr[i-1]을 포함할 수 있기 때문에, 연속해서 세 개의 계단을 밟는 경우가 발생할 위험이 있다.

예를 들어, dp[i-1]이 dp[i-2] + arr[i-1]을 사용했다면, dp[i] = dp[i-1] + arr[i]를 적용하면
👉 arr[i-2], arr[i-1], arr[i]를 연속으로 밟는 문제 발생

 

(2) 가장 작은 문제의 답 구해 놓기

dp[0] : 첫 계단을 밟는 경우 == arr[0]
dp[1] : 첫 계단, 두 번째 계단을 밟는 경우 == arr[0] + arr[1]

(3) 값 기록해 나가기

N까지 차례로 값 계산
이때 층계가 총 2개 이하인 경우 index out of error가 발생할 수 있으니 예외 처리**

 

DP의 시간 복잡도

위 방식으로 문제를 풀면 N번의 연산 필요 → O(N)
N 최대 300 → 연산 약 300개 필요

 

정답 코드

import sys
input = sys.stdin.readline

n = int(input())
stairs = [int(input()) for _ in range(n)]

if n < 2 :
    print(stairs[n-1])
else :
    dp = [0] * n

    dp[0] = stairs[0]
    dp[1] = stairs[0] + stairs[1]

    for i in range(2, n) :
        dp[i] = max(dp[i-2], dp[i-3] + stairs[i-1]) + stairs[i]

    print(dp[n-1])
저작자표시