dp같아 보이는 bfs문제이다. N이 K에 도착했을 때 최소 시간을 구하는 문제로 처음에 dp로 접근해서 생각을 하느라 시간이 좀 걸렸다. 생각해보니 굳이 dp를 쓸게 아니라 bfs로 제일 먼저 K에 도착한 것이 최소 시간이 된다는 것을 깨닫고 bfs로 풀었다. -1, +1, *2
세가지 경우로 bfs를 돌며 이미 지나온 값은 먼저 지나갔기에 더 짧은 시간이므로 다시 큐에 넣지 않도록 check
함수로 구분했다.
#include <iostream>
#include <queue>
using namespace std;
int N, K, res = 0;
int dir[2] = { -1,1 };
bool check[100000];
void bfs() {
queue<pair<int, int>> q;
q.push({ N,0 });
check[N] = true;
while (!q.empty()) {
int cur = q.front().first;
int time = q.front().second;
q.pop();
if (cur == K) {
res = time;
break;
}
for (int i = 0; i < 3; i++) {
int next;
if (i == 2) {
next = cur * 2;
}
else {
next = cur + dir[i];
}
if (next < 0 || next > 100000) continue;
if (check[next]) continue;
q.push({ next,time + 1 });
check[next] = true;
}
}
}
void solution() {
bfs();
cout << res;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> N >> K;
solution();
return 0;
}