알고리즘 분류
- DP
- 다익스트라
풀이
점화식은 위치가 짝수일 때와 홀수일 때로 나뉜다.
- 짝수일 때
- 1칸 이전 값 (가중치 1)
- 절반 위치 (가중치 0)
- 홀수일 때
- 1칸 이전 값 (가중치 1)
- 1칸 앞(짝수)의 절반 위치(가중치 1)
하지만 홀수의 점화식에 의문이 들 수가 있다.
왜 1칸 앞의 절반만 고려할까? 문제에서는 앞이나 뒤로 1칸씩 이동할 수 있다고 했는데?
2로 나눈 값이 올림 또는 내림이 될 수 있는 거 아니야?
왜 "1칸 뒤(짝수)의 절반 위치"는 고려하지 않을까?
결론부터 말하자면 점화식에 1칸 뒤 절반 위치를 넣어도 결과는 동일하다.
하지만 의미 없는 연산이다. 이유는 "1칸 이전 값"과 중복되기 때문이다.
예를 들어 현재 위치가 9라고 가정해 보자.
- 1칸 이전 값 → 9-1 = 8
- 1칸 뒤(짝수)의 절반 위치 → (9-1)/2 = 4
중요한 사실은 2배 이동은 가중치가 그대로이다.
그렇기 때문에 8의 위치와 4의 위치 값이 같기 때문에
- 8의 위치 = 4의 위치
- 1칸 이전 값 = 1칸 뒤(짝수)의 절반 위치
홀수일 때 위 등식이 성립한다.
사실 처음에는 떠올리지 못했다.
정답 처리를 받았을 때는 점화식에 같이 포함시켰는데 생각해 보니 필요가 없었다.
풀이 코드
DP
#include <iostream>
using namespace std;
int main(){
int n, k, dp[100001];
cin>> n >> k;
// 시작점에서 뒤로 이동
for(int i = 0; i <= n; i++)
dp[i] = n-i;
// 앞으로 이동
for(int i= n+1; i <= k; i++) {
// 1칸 이동
dp[i] = dp[i-1] + 1;
// 2배 이동
if(i%2 == 0) // 짝수
dp[i] = min(dp[i], dp[i/2]);
else // 홀수
dp[i] = min(dp[i], dp[(i+1)/2] + 1);
}
cout << dp[k];
}
다익스트라
#include<bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
bool visited[100001];
int main(){
int n,k;
priority_queue<pii, vector<pii>, greater<pii> > pq;
cin >> n >> k;
visited[n] = true;
pq.push({0, n});
while(!pq.empty()) {
int cur=pq.top().second;
int cost=pq.top().first;
pq.pop();
if(cur == k) {
cout << cost;
break;
}
// 점프
if(cur*2 <= k+1 && !visited[cur*2]) {
visited[cur*2] = true;
pq.push({cost, cur*2});
}
// 앞으로
if(cur+1 <=k && !visited[cur+1]) {
visited[cur+1] = true;
pq.push({cost+1, cur+1});
}
// 뒤로
if(cur-1 >= 0 && !visited[cur-1]) {
visited[cur-1] = true;
pq.push({cost+1, cur-1});
}
}
}
후기
음.. 사실 이 문제를 처음 봤을 때 DP 밖에 떠오르지 않아서 힘들게 점화식을 구했다.
다익스트라로 푸는 방법이 있는지 떠올리지 못했다.
이번 문제야 다행히 풀렸지만 한 알고리즘에 꽂히면 헤어 나오지를 못하겠다.
만약 코테에서 떠오른 알고리즘으로 접근했는데 이 방법으로는 절대 풀 수 없으면... 생각만으로도 어지럽다
(+)
코드가 짧다고 다 좋은 건 아니지만 숏코딩 1등!
