[leetCode] 746. Min Cost Climbing Stairs - javascript

 

문제

You are given an integer array cost where cost[i] is the cost of ith step on a staircase. Once you pay the cost, you can either climb one or two steps.

You can either start from the step with index 0, or the step with index 1.

Return the minimum cost to reach the top of the floor.

 

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 2:

Input: cost = [1,100,1,1,1,100,1,1,100,1]
Output: 6
Explanation: You will start at index 0.
- Pay 1 and climb two steps to reach index 2.
- Pay 1 and climb two steps to reach index 4.
- Pay 1 and climb two steps to reach index 6.
- Pay 1 and climb one step to reach index 7.
- Pay 1 and climb two steps to reach index 9.
- Pay 1 and climb one step to reach the top.
The total cost is 6.

 

 

 

해결방법

DP 관련 문제라는 걸 알았지만 자료구조관련 책도 읽었지만 진짜 하나도 기억이 나지 않는 소오름~

그래서 그림으로 하나하나 그림. 주어진 문제에 따르면 일단 제일 끝 탑이 어디인지 모름. 그 탑을 가기 위해서 탑 기준을 여러개로 잡고 그림. 예시로 준 것을 기준으로 풀었는데, 지불할 페이. 그리니깐 탑을 향해 갈 방법이 여러개라서 값도 여러 개 나와서 그 중에 최소값을 구하면 된다는 거까지는 이해완료. 

 

그런데 결국엔 코드화하는 과정진도를 전혀 빼지 못 했다. 문제를 이해하는 것 조차 꽤나 시간이 걸렸는데 이게 easy 문제라서 더 멘붕. 진짜..어카냐 나.... 

 

아래링크된 강의도 봄

 

 

 

 

 

 

 

솔루션 

var minCostClimbingStairs = function(cost) {
    const n = cost.length
   
    // 스텝값을 넣을 배열
    const dp = []
    dp[0] = cost[0]
    dp[1] = cost[1]
    
    //0,1이 있으니깐 그 다음값을 구하기 위한 과정.....인데....
    // bottom up 방식으로 들어가니깐...
    for (let i = 2; i < n; i++) {
        //  = 20 + min(10,15) 결국엔 30이 됨. 10에서 20으로 뛰고 그 다음 넘어갔을경우값
        // 그 다음 3을 구할 필요가 없는 이유는 3의 값이 작다고 할지라도 0,1,2 다 거쳐간 만큼의 값이 나옴 
        dp[i] = cost[i] + Math.min(dp[i - 2], dp[i - 1]);
    }
    // 탑으로 갔을 때의 지불된 스텝값 중에 최소값을 반환하기 위해 length값을 기준으로 
    return Math.min(dp[n - 1], dp[n - 2])

};

 

1. 지불한 값을 저장한 배열 만듬

2. cost[0]에서 진행한다고 봤을 때, cost[1]에서 진행한다고 봤을 때 두가지를 넣어준다. 주어진 계단이 length가 2를 넘을 거기때문에 신경안써도 됨

3. 출발점들을 베이스로 두고 위로 점프했을 때 스텝값을 구함.  

4. 마지막 탑 지점이 주어진 cost의 끝자리라는 기준으로해서 그 앞자리를 값들을 찾아서 그 중에 최소값

 

 

 

진짜 나 어카냐... 관련 비슷한 문제를 더 풀어봐야한다. ... !! 나는 바보가 아니다!! 나는 바보가 아니야!!! 아자아자!!!