[프로그래머스] 최소 비용으로 계단 오르기 (java, DP)

문제

문제 설명
당신은 계단의 각 단계에서 지불해야 하는 비용이 담긴 정수 배열 cost를 받았습니다. cost[i]는 i번째 단계의 비용을 나타냅니다. 비용을 지불한 후, 한 계단 또는 두 계단을 오를 수 있습니다.

0번 인덱스의 단계에서 시작할 수도 있고, 1번 인덱스의 단계에서 시작할 수도 있습니다.

층의 꼭대기에 도달하기 위한 최소 비용을 반환하세요.

제한 사항

2 <= cost.length <= 1000
0 <= cost[i] <= 999

입출력 예

cost	return
[10, 15, 20]	15
[1, 100, 1, 1, 1, 100, 1, 1, 100, 1]	6

입출력 예 설명

입출력 예#1

인덱스 1에서 시작합니다.
15를 지불하고 두 계단을 올라 꼭대기에 도달합니다.
총 비용은 15입니다.

입출력 예#2

인덱스 0에서 시작합니다.
1을 지불하고 두 계단을 올라 인덱스 2에 도달합니다.
1을 지불하고 두 계단을 올라 인덱스 4에 도달합니다.
1을 지불하고 두 계단을 올라 인덱스 6에 도달합니다.
1을 지불하고 한 계단을 올라 인덱스 7에 도달합니다.
1을 지불하고 두 계단을 올라 인덱스 9에 도달합니다.
1을 지불하고 한 계단을 올라 꼭대기에 도달합니다.
총 비용은 6입니다.

문제 분석

문제 파악

• 계단을 한 번에 1~2개 뛸 수 있다.
• 각 단계에서 지불해야 하는 비용이 담긴 배열 : 0<=cost[i]<=999
• 층의 꼭대기에 도달하기 위한 최소 비용 구하기

접근 방법

• 각 위치까지 최소 거리를 저장하는 배열 dp (메모이제이션)
• 계단을 1~2칸 오를 때, 현재 위치까지 도달하는데에는 전 인덱스, 전전 인덱스의 영향을 받게 된다. (그림 참조)

→ 최솟값이 되려면 영향을 받고 있는 것 중 최소/최댓값을 가져와 연산한다.

• dp의 마지막 인덱스에서 1칸 이동하면 도착지이고, 마지막 인덱스 -1 에서 2칸 이동하면 도착지이므로 마지막 인덱스와 마지막 인덱스 -1 에서 최솟값을 구하면 된다.

 

정답 코드

import java.util.*;

class Solution {
    public int solution(int[] cost) {
        int answer = 0;
        int[] dp = new int[cost.length+1];
        // Arrays.fill(dp, Integer.MAX_VALUE);
        
        // basecase
        dp[0] = cost[0];
        dp[1] = cost[1];
        
        // 점화식
        for(int i=2; i<cost.length; i++) {
            dp[i] = Math.min(dp[i-2], dp[i-1]) + cost[i];
        }
        
        return Math.min(dp[cost.length-1], dp[cost.length-2]);
    }
}

교훈점

• DP 의의 : 반복되는 연산을 저장하여 줄여준다. (메모이제이션)
• DP 성질 : 현재 위치까지 도달하는데에는 이전의 영향을 받는다.