수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다.
수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.
#include <iostream>
#define INF 987654321
#define MAX 100002
using namespace std;
int N, K;
int memo[MAX];
int main() {
cin >> N >> K;
for (int i = 0; i < MAX; i++) {
memo[i] = INF;
}
memo[0] = N;
for (int i = 1; i < MAX; i++) {
// N보다 작은 경우를 구하는 DP,
if (i < N) {
memo[i] = N - i;
}
// N보다 큰 경우를 구하는 DP.
// n = k_1 + 1, n = k_2 - 1, n = k_3 * 2 => k1 = n-1, k2 = n+1, k3 = n/2
else if (i == N) memo[i] = 0;
else {
if (i%2 == 0) {
memo[i] = min(min(memo[i+1]+1, memo[i-1]+1), memo[i/2]);
}
else {
memo[i] = min(memo[i+1]+1, memo[i-1]+1);
}
}
int idx = i*2;
while (idx < MAX) {
memo[idx] = min(memo[idx], memo[i]);
idx = idx*2;
}
}
cout << memo[K];
return 0;
}
도착지점 | 비용 |
---|---|
1 | |
1 | |
0 |
d[K]
를 출력하면 답이 된다.#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#define MAX 100001
using namespace std;
int N, K;
int d[MAX];
int isRange(int node) { return node >= 0 && node < MAX; }
void dijk() {
priority_queue<pair<int, int> > que;
fill(d, d+MAX, -1);
d[N] = 0;
que.push(make_pair(0, N));
int near_cost[3] = {1, 1, 0};
int near_node[3];
while (!que.empty()) {
int top_node = que.top().second; int top_cost = -que.top().first;
que.pop();
if (d[top_node] < top_cost) continue;
near_node[0] = top_node-1; near_node[1] = top_node+1; near_node[2] = top_node*2;
for (int i = 0; i < 3; i++) {
if (isRange(near_node[i])) {
if (d[near_node[i]] > top_cost + near_cost[i] || d[near_node[i]] == -1) {
d[near_node[i]] = top_cost+near_cost[i];
que.push(make_pair(-d[near_node[i]], near_node[i]));
}
}
}
}
}
int main() {
cin >> N >> K;
dijk();
cout << d[K];
return 0;
}