LeetCode - 746. Min Cost Climbing Stairs

문제: 746. Min Cost Climbing Stairs (Easy)

 

1. 계단의 비용을 나타내는 cost 배열이 제공됨.
2. 해당 비용을 내고 한 계단 또는 두 계단을 오를 수 있음.
3. 인덱스가 0이거나 1부터 시작할 수 있고, 꼭대기에 도달하기 위한 최소 비용을 리턴.

Example 1:
Input: cost = [10,15,20] Output: 15 Explanation: You will start at index 1. - Pay 15 and climb two steps to reach the top. The total cost is 15.

 

예시:

 

Example 1:
Input: cost = [10,15,20]

Output: 15

Explanation: 인덱스 1에서 시작하여 2계단을 한번에 오른 값인 15가 최소 비용.

 

 

풀이:

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        for (int i = 2; i < cost.length; i++) {
            cost[i] = Math.min(cost[i - 2], cost[i - 1]) + cost[i];
        }

        return Math.min(cost[cost.length - 1], cost[cost.length - 2]);
    }
}

 

설명:

 

1. 3번째 인덱스부터 시작하여 두번째 전 비용과 바로 전 비용 중 최소값과 현재 계단의 비용을 합하여 누적.

2. 전부 누적 후 꼭대기 값을 계산하기 위해 두번째 전 비용과 바로 전 비용 중 최소값을 리턴.

 

시간복잡도: O(n)

공간복잡도: O(1)

 

Runtime: 0ms Beats 100.00% of users with Java

Memory: 42.93MB Beats 65.39% of users with Java

 

 

---

개인의 해답으로 풀이한 문제입니다. 
절대적인 정답이 아닐 수 있으며, 더 좋은 개선 방안이 있다면 댓글로 의견 주세요.