[TIL] 동적계획법

 

* 문제
계단 배열이 주어졌을 때, 계단을 올라가는 최소 비용을 계산하는 문제입니다.
배열의 각 요소는 해당 계단을 밟을 때의 비용을 나타냅니다.
계단은 한 번에 한 계단 또는 두 계단씩 오를 수 있으며, 배열의 마지막이나 마지막에서 두 번째 인덱스에서 도착하는 것이 목표입니다.

* 조건
1. 2 <= cost.length <= 1000
2. 0 <= cost[i] <= 999

* 예시
예제 1:
	입력: cost = [10, 15, 20]
	출력: 15
	설명: 인덱스 1에서 시작하여 15의 비용으로 마지막에 도달합니다.

예제 2:
	입력: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
	출력: 6
	설명: 경로는 0, 2, 4, 6, 7, 9 순으로 1 + 1 + 1 + 1 + 1 + 1의 비용을 소모합니다.

이 문제를 보고 처음에는 세 개의 숫자를 다 비교해야 하나?
어떻게 비교를 하고 더 작은 숫자를 선택해서 그 다음 인덱스를 비교해야 하지?
어떻게 접근해야 맞을지 생각이 잘 떠오르지 않았다.

접근 방식

동적 계획법(DP)을 사용하여, dp[i]에 i번째 계단까지 올라가는 최소 비용을 저장합니다.
초기화로 dp[0]과 dp[1]을 각각 cost[0]과 cost[1]로 설정합니다.
각 계단 i에 대해 dp[i] = cost[i] + min(dp[i-1], dp[i-2])로 누적 비용을 계산합니다.
마지막 도착 지점은 dp[n-1]과 dp[n-2] 중 최소값입니다.

dp는 cost와 같은 길이의 리스트로
리스트의 길이만큼 0으로 채운 후 누적값을 계산하여 저장한다.

동적계획법

- 큰 문제를 작은 하위 문제로 나누고, 이 하위 문제들의 결과를 저장하여 재사용함으로써 효율적으로 해결하는 알고리즘 설계 기법.
- 중복 계산을 줄여 복잡한 문제를 더 빠르게 해결할 수 있다.
- 피보나치 수열 등에 활용

여기서 동적 계획법이란
내가 처음에 생각한대로 계속해서 숫자를 비교하며 연산을 늘리는 것 대신
값을 누적해서 비교함으로써 연산을 줄일 수 있는 효율적인 방법.

계단은 최대 두 계단씩 오를 수 있기때문에
dp의 dp[0]와 dp[1]의 값을 우선 cost[0]과 cost[1]로 채워준다.

값을 채운 후 그 다음 인덱스부터 값을 누적해주는데
cost[0]과 cost[1] 중에서 더 작은 값을 더해준다.

그렇게 마지막까지 누적해서 값을 저장한 후
dp[cost.length-1]과 dp[cost.length-2]의 값 중 더 작은 값을 반환해주면 된다.

알고리즘을 이해하고 나니 어떻게 풀어야 하는 문제였는지 이해가 갔다.

정답 코드

int minCostClimbingStairs(List<int> cost) {
  int n = cost.length;
  if (n == 2) return cost.reduce((a, b) => a < b ? a : b); // 계단이 2개인 경우 최소값 반환

  List<int> dp = List<int>.filled(n, 0);
  dp[0] = cost[0];
  dp[1] = cost[1];

  for (int i = 2; i < n; i++) {
    dp[i] = cost[i] + (dp[i - 1] < dp[i - 2] ? dp[i - 1] : dp[i - 2]);
  }

  return dp[n - 1] < dp[n - 2] ? dp[n - 1] : dp[n - 2];
}