CodingTest/LeetCode

[LeetCode] 746. Min Cost Climbing Stairs, Easy

뜸부깅 2025. 4. 30. 16:29
반응형

1. 문제

  • 각 계단을 오르는 비용이 정수 배열 cost로 주어질 때, 정상에 도달할 수 있는 최소 비용을 반환하라.

2. 해결

function minCostClimbingStairs(cost: number[]): number {
    const dp = [cost[0], cost[1]];

    for(let i = 2; i < cost.length; i++) {
        dp[i] = Math.min(dp[i-1], dp[i-2]) + cost[i];
    }

    return Math.min(dp[cost.length-1], dp[cost.length-2]);
};
  • 계단의 시작은 0번 인덱스 혹은 1번 인덱스부터 시작할 수 있기 때문에, dp에서 해당 코스트를 미리 채워둔다.
  • 이후 특정 인덱스에 도달할 수 있는 방법은 직전 인덱스에서 오거나 2계단 전에서 올라오는 경우이다.
  • 최소 코스트를 구해야 하므로 두 경우 중 최소값을 취하고, 해당 계단의 코스트를 더해 도달할 수 있는 최소 비용을 쭉 구한다.
  • 마찬가지로 정상에 도달할 수 있는 경우의 수는 바로 직전 혹은 2단계 전에서 오는 방법이므로, 두 경우 중 가장 작은 비용을 구하면 정답.