Min Cost Climbing Stairs
DP 문제를 풀고싶어서 접근했던 문제인데 점화식을 찾아내는걸 보니 어느정도 감을 잡은것 같기도 하다
On a staircase, the i-th step has some non-negative cost cost[i] assigned (0 indexed).
Once you pay the cost, you can either climb one or two steps. You need to find minimum cost to reach the top of the floor, and you can either start from the step with index 0, or the step with index 1.
계단 하나를 오를때 비용이 발생하고, 한번에 하나 혹은 두개의 계단을 오를 수 있다.
[10, 15, 20] 이면 15만 지불하고 모든 계단을 다 오를 수 있는 것인데 가장 최소의 비용을 지불하고 계단을 전부 오르려면 어떻게 해야하는가?
나에게 가장 큰 힌트가 된 것은 이 예시이다
Input: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
Output: 6
Explanation: Cheapest is start on cost[0], and only step on 1s, skipping cost[3].
Plain Text
복사
이렇게 각 단계별로 접근을 했다.
1.
계단을 마지막(n)까지 오르려면 그 이전에 올라와야 하는 계단은 어디인가?
2.
1번의 답이 n-1 이라면 n-1 이전에 어디까지 올라가야 할까?
3.
2번의 n-3 이라면 n-3 이전에 어디까지 올라가야 할까?
이렇게 접근하다 보니 점화식이 어느정도 만들어졌다.
n 번째 계단에 오르는 비용을 저장한 배열 pay 가 있을때 n번째 계단의 비용을 구하는 점화식은 다음과 같다
→ pay[n] 을 반환하면 되겠다고 생각했다.
주어진 예시 [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] 의 비용 pay는 다음과 같다
[?, ?, 2, 3, 3, 103, 4, 5, 104, 6]
첫번째 계단과 두번째 계단의 비용을 ? 로 해두었다. 무엇으로 해야할지 감이 안왔기 때문이다.
최초의 내 생각은 이러했다.
[10, 15, 20] 을 보며 pay[2] = min(cost[1], cost[0] + cost[2]) 가 아닐까?
하지만, 이것은 length 가 3인 경우에는 합리적일지 모르지만, 3보다 큰 경우엔 말이 되지 않는다.
주어진 조건이 이러하다
pay[0] 과 pay[1] 을 구하지 못한다면 pay[n] 을 구할 수 없다. 지금 접근이 bottom up 방식인데 base case 를 정의하지 못하면 무슨 pay[n] 을 구하겠는가
→ pay[n] 을 반환하면 되겠다고 생각했다.
이 생각이 잘못 된 생각이다. 반환은 min(pay[n], pay[n-1]) 중에 최소값이면 된다.
즉, pay[0], pay[1] 중에 최소값이 반환 되어야 한다 pay[1] 에 터무니 없이 비싼 가격이 와도 상관없다.
min 함수를 통해 최적의 값을 찾아줄 테니까
class Solution {
public int minCostClimbingStairs(int[] cost) {
int[] pay = new int[cost.length];
pay[0] = cost[0];
pay[1] = cost[1];
for (int i = 2; i < cost.length; i ++) {
pay[i] = Math.min(pay[i-1], pay[i-2]) + cost[i];
}
int last = cost.length - 1;
return Math.min(pay[last], pay[last-1]);
}
}
Java
복사
