문제 이해하기
계단 오르기 최소 비용(Min Cost Climbing Stairs) 문제는 다음과 같습니다. 계단의 i번째 칸마다 음수가 아닌 비용 cost[i]가 할당되어 있으며, 비용을 지불하면 한 칸 또는 두 칸을 오를 수 있습니다. 목표는 계단 꼭대기(floor top)에 도달하는 데 드는 최소 비용을 구하는 것이고, 시작 위치는 인덱스 0 또는 인덱스 1의 계단 중에서 자유롭게 선택할 수 있습니다.
예시
예를 들어 입력이 cost = [12, 17, 20]이라면 출력은 17입니다. 인덱스 1(비용 17)에서 출발해 두 칸을 오르면 바로 꼭대기에 도달할 수 있고, 이때의 비용이 가장 저렴하기 때문입니다.
해결 전략: 동적 프로그래밍(DP)
이 문제는 동적 프로그래밍으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- dp[i]: i번째 계단에 도달할 때까지 지불한 최소 누적 비용
- i번째 계단은 바로 아래(i−1) 또는 두 칸 아래(i−2)에서 올라올 수 있으므로, 두 경로 중 더 작은 값에 현재 계단의 비용을 더합니다.
알고리즘 단계
- cost와 같은 크기의 배열 dp를 생성하고 0으로 초기화합니다.
- dp[0] := cost[0]
- cost의 길이가 2 이상이면 dp[1] := cost[1]
- i가 2부터 cost 길이 − 1까지 순회하며 dp[i] := cost[i] + min(dp[i−1], dp[i−2])를 계산합니다.
- 최종적으로 min(dp[-1], dp[-2])를 반환합니다. 꼭대기는 마지막 계단에서 한 칸 또는 두 칸을 오르면 되므로, 마지막 두 값 중 작은 것이 곧 정답입니다.
Python 구현 코드
아래 예제를 통해 더 잘 이해해 보겠습니다.
class Solution:
def minCostClimbingStairs(self, cost):
dp = [0] * len(cost)
dp[0] = cost[0]
if len(cost) >= 2:
dp[1] = cost[1]
for i in range(2, len(cost)):
dp[i] = cost[i] + min(dp[i-1], dp[i-2])
return min(dp[-1], dp[-2])
ob = Solution()
print(ob.minCostClimbingStairs([12,17,20]))
입력
[12,17,20]
출력
17
복잡도 분석 및 추가 팁
위 알고리즘은 모든 계단을 한 번씩만 순회하므로 시간 복잡도는 O(n), dp 배열을 사용하므로 공간 복잡도 역시 O(n)입니다. 만약 공간을 절약하고 싶다면 dp 배열 대신 직전 두 값(prev1, prev2)만 저장하는 방식으로 최적화하여 공간 복잡도를 O(1)로 줄일 수 있습니다. 동적 프로그래밍의 대표적인 유형인 이 문제는 코딩 테스트에서 자주 등장하니, 점화식을 손으로 직접 유도해 보며 연습해 보는 것을 추천합니다.