[백준] 16953번. A →B

[백준] 16953번. A →B

1. 문제

정수 A를 B로 바꾸려고 한다. 가능한 연산은 다음과 같은 두 가지이다.

• 2를 곱한다.
• 1을 수의 가장 오른쪽에 추가한다.

A를 B로 바꾸는데 필요한 연산의 최솟값을 구해보자.

2. 입력

첫째 줄에 A, B (1 ≤ A < B ≤ 10^9)가 주어진다.

3. 출력

A를 B로 바꾸는데 필요한 연산의 최솟값에 1을 더한 값을 출력한다. 만들 수 없는 경우에는 -1을 출력한다.

4. 풀이

• BFS로 풀었다.
• queue에서 꺼낸 값을 2배 한 값과 10배 +1 한 값 중 목표 값과 같은 것이 있다면 해당 depth를 기록하고 반복 종료
• 목표 값이 다르다면 목표 값보다 작으면 큐에 넣고, 목표 값보다 크면 큐에 넣지 않는다.
• 처음 depth 값을 -1로 설정하면 목표 값을 찾을 수 없는 경우 depth를 출력하면 자동으로 -1이 출력된다.

5. 처음 코드와 달라진 점

• A와 B의 최댓값이 10^9이라 2배해도 int 범위 안이라고 생각했다.
• 수의 가장 오른쪽에 1을 추가하는 연산은 int 범위를 넘어간다.
• depth는 int 범위 안이므로 숫자만 long long으로 바꾸어주었다.

6. 코드

#include <iostream>
#include <queue>
#define INF 1e9

using namespace std;

int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	
	int start, target;
	cin >> start >> target;

	queue<pair<long long, int>> q;
	q.push({ start,1 });

	int min_depth = -1;
	while (!q.empty()) {
		long long x = q.front().first;
		int depth = q.front().second;
		q.pop();

		long long attached_number = x * 10 +1;
		long long doubled_number = x * 2;

		if (attached_number == target || doubled_number == target) {
			min_depth = depth + 1;
			break;
		}
		if (attached_number < target) q.push({ attached_number, depth + 1 });
		if (doubled_number < target) q.push({ doubled_number, depth + 1 });

	}

	cout << min_depth;
}