[LeetCode] 746. Min Cost Climbing Stairs

[문제 링크]

https://leetcode.com/problems/min-cost-climbing-stairs/description/

 

[문제]

각 계단마다 일정한 비용이 들며, 계단을 오르는 데 드는 최소 비용을 구하는 문제입니다.

계단 배열 cost가 주어집니다. 인덱스 0 또는 1에서 출발할 수 있습니다. 한 번에 1칸 또는 2칸을 이동할 수 있습니다. 마지막 계단을 꼭 밟을 필요는 없으며, 정상에 도착하는 것이 목표입니다. 최소 비용으로 계단을 오르는 방법을 찾아야 합니다.

[풀이 과정]

모든 경우를 구하되 구했던 걸 또 구하지 않고 풀어야겠다고 생각하고 접근했다.

 

[코드]

class Solution {
    int[] memo;
    public int minCostClimbingStairs(int[] cost) {
        int n = cost.length;
        memo = new int[n+1];
        memo[0] = cost[0];
        memo[1] = cost[1];

        for(int i = 2; i < n; i++) {
            memo[i] = Math.min(memo[i-1], memo[i-2]) + cost[i];
        }

        if(memo[n-1] > memo[n-2]) {
            return memo[n-2];
        } 

        return memo[n-1];
    }

}

[회고]

방법을 생각해내니까 쉬웠습니다!

 

 

 

 

질문과 피드백은 언제나 환영입니다.

감사합니다.