BOJ 16953 - A → B

문제 링크

문제#

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

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

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

입력#

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

출력#

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

풀이#

가능한 연산이 2를 곱하기, 1 붙이기 두 가지뿐이라서 현재 값에서 갈 수 있는 다음 상태도 매우 단순하다. 이 코드에서는 cur * 2, cur * 10 + 1 두 경우를 재귀적으로 뻗어 가며 답을 찾는다.

중요한 건 가지치기다. 현재 값이 이미 B를 넘었다면 더 내려가 봐야 의미가 없고, 이미 찾은 최솟값보다 깊이가 깊어져도 더 좋은 답은 나오지 않는다. 그래서 cur < b, depth <= cnt 조건으로 탐색 범위를 꽤 많이 줄인다.

문제 분류상 BFS로 보는 해설도 가능하지만, 현재 구현은 깊이를 함께 넘기는 DFS에 가깝다. 연산이 값만 키우는 방향으로 진행되기 때문에 이런 식으로 완전탐색을 하더라도 가지치기만 잘 걸면 충분히 답을 구할 수 있다.

코드#

#include <iostream>
using namespace std;
 
int a, b, cnt = 10001;
 
void bfs(long long cur, int depth) {
 
	if (cur == b) 
		cnt = (depth < cnt) ? depth : cnt;
 
	if (cur < b && depth <= cnt) {
		bfs(cur * 2, depth + 1);
		bfs(cur * 10 + 1, depth + 1);
	}
}
 
void solve() {
	
	cin >> a >> b;
	bfs(a, 1);
 
	if (cnt == 10001)
		cnt = -1;
 
	cout << cnt << '\n';
 
}
 
int main() {
 
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
 
	solve();
 
	return 0;
}

복잡도#

• 시간 복잡도: 두 연산을 재귀적으로 탐색하므로 최대 깊이를 $D$라 할 때 최악의 경우 $O(2^D)$이다. 값이 계속 커져 $B$를 넘으면 가지치기되므로 $D$는 $O(\log B)$ 범위에 묶인다.
• 공간 복잡도: 재귀 호출 깊이만 사용하므로 $O(D)$이다.

마무리#

가능한 수만 뻗어 가되 목표를 넘는 가지를 바로 자르는 것이 이 코드의 핵심이다.