문제
N개의 계단이 있고 각 계단 위에는 임의의 정수가 적혀있다.
철수는 첫 번째 계단에서 마지막 계단까지 올라가려 하는데 한 번에 오를 수 있는 계단수는 1개 또는 2개이다.
계단을 오르는 비용이 (현재 계단에 적혀있는 정수) - (옮겨갈 계단에 적혀있는 정수)의 절대값이라고 할 때
최소 비용을 구하시오.
풀이
일단 각 계단에 적힌 정수를 h(i)라고 하자.
그러면 첫 번째 위치 h(1)에서
한 계단을 오르는 비용은 |h(1) - h(2)| 이고
두 계단을 오르는 비용은 |h(1) - h(3)| 이 된다.
제일 먼저 떠오르는 순진한 방법은 greedy하게 각 계단에서 비용이 적은 층으로 옮겨가는 것이다.
즉, 단순히 각 계단에서 한 계단 오르는 비용과 두 계단 오르는 비용 중에서 적은 방법을 선택해서 끝까지 가는 것이다.
하지만 greedy를 선택할 때는 항상 소탐대실을 주의해야 한다.
당장의 이익이 커보이지만 전체적으로는 최적이 아닐 수 있기 때문이다.
greedy는 구현이 쉽지만 이게 정말 최적인지를 고민해 봐야 한다.
여기서는 최적이라고 쉽게 확신할 수 있는 동적계획법으로 풀어보도록 하겠다.
우리가 찾고자 하는 값은 1번째 위치에서 N번째 위치로 가는 최소값이다.
이를 f(N)이라고 하자.
f(N) = min(
f(N-1) + |h(N-1) - h(N)|,
f(N-2) + |h(N-2) - h(N)|)
이 된다.
해석하자면 N-1번째 계단까지 가는 최소비용에서 1칸을 뛰는 비용과 N-2번째 계단까지 가는 최소비용에서 2칸을 뛰는 비용 중 적은 값이 N까지 가는 최소값인 것이다.
첫 몇 계단에 대한 비용을 생각해보자.
f(1) = h(1)
f(2) = |h(1) - h(2)|
f(3) = min(
f(2) + |h(2) - h(3)|,
f(1) + |h(1) - h(3)|)
f(4) = min(
f(3) + |h(3) - h(4)|,
f(2) + |h(2) - h(4)|)
위와 같은 패턴으로 f(1)과 f(2)는 시작값으로 설정하고 이어지는 f(3)부터는 위의 값들을 재활용하여 점점 채워나갈 수 있다.
이는 다음과 같은 수도코드로 작성할 수 있다.
int calcMininumCostToGetStepN(int N, int[] height) {
int dp[] = new dp[N];
dp[0] = height[0]
dp[1] = abs(height[0] - height[1]);
for (int i = 2; i < N; i++) {
dp[i] = min(dp[i-1] + abs(height[i-1] - height[i]),
dp[i-2] + abs(height[i-2] - height[i]));
}
return dp[N-1];
}한편 다음과 같이 관계식을 그대로 재귀함수로 옮겨서 구현할 수도 있다.
f(i) = min(
f(i-1) + |h(i-1) - h(i)|,
f(i-2) + |h(i-2) - h(i)|)
int dp[] = new dp[N];
int calcRecurMininumCostToGetStepN(int N, int[] height) {
if (N == 0) {
dp[0] = height[0];
return dp[0];
}
else if (N == 1) {
dp[1] = abs(height[0] - height[1]);
return dp[1];
}
dp[N-1] = min(calcRecurMininumCostToGetStepN(N-1 + abs(height[i-1] - height[i]),
calcRecurMininumCostToGetStepN(N-2 + abs(height[i-2] - height[i]));
return dp[N-1];
}이때 중요한 것은 메모이제이션을 해서 중복연산을 방지하는 것이다.
회고
동적계획법 문제를 푸는 첫 번째 접근법은 원하는 답을 f(i)로 정의해 보는 것이다.
이 문제에서는 N번째 계단까지 가는 최소비용을 f(i)로 정의했다.
그러고 나서 f(i)가 f(i-1), f(i-2)...와 같이 이전값들과 어떤 관계가 있는지 살펴본다.
그래서 f(i)를 이전 값들을 사용해 관계식을 설정할 수 있으면 동적계획법으로 풀 수 있는 문제에 해당한다.
