💡 너비 우선 탐색/그래프 이론/그래프 탐색/그리디 알고리즘
Memory 1116KB Time 0ms Code Length 507B
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <stdio.h>
#include <algorithm>
#include <queue>
#define min(a,b) a>b?b:a
using namespace std;
int MIN = 1e9;
void dfs(long long a, long long b, int cnt) {
if (a == b) {
MIN = min(MIN, cnt);
return;
}
if (a > b) {
return;
}
dfs(a * 2, b, cnt + 1);
dfs(a * 10 + 1, b, cnt + 1);
}
int main() {
long long from, to;
scanf("%lld %lld", &from, &to);
getchar();
dfs(from, to, 1);
// 변화 하지 않았다면??
if (MIN == 1e9) {
printf("-1\n");
}
else {
printf("%d\n", MIN);
}
}
이 코드는 주어진 두 수 사이에 있는 수를 만들기 위해 2를 곱하거나 1을 뒤에 추가하는 두 가지 연산을 사용하여 최소 횟수로 만들어내는 프로그램이다. 주어진 두 수를 입력받은 후, 깊이 우선 탐색(DFS)을 이용하여 가능한 모든 경우를 탐색하면서 목표 수에 도달할 때까지 연산을 수행한다. 이때 최소 횟수를 구하기 위해 현재까지의 연산 횟수를 인자로 넘겨주며, 최소 횟수를 찾으면 이를 갱신한다. 만약 목표 수에 도달할 수 없는 경우에는 -1을 출력하고, 그렇지 않으면 최소 횟수를 출력한다.
