BOJ 16953 - A->B

https://www.acmicpc.net/problem/16953

16953번: A → B

BOJ 16953 - A->B

 

문제 설명

A → B

시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율

2 초

512 MB

10871

4660

3710

41.053%

문제

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

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

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

입력

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

출력

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

예제 입력 1 복사

2 162

예제 출력 1 복사

5

2 → 4 → 8 → 81 → 162

예제 입력 2 복사

4 42

예제 출력 2 복사

-1

예제 입력 3 복사

100 40021

예제 출력 3 복사

5

100 → 200 → 2001 → 4002 → 40021

 

문제 풀이

DFS로 완전 탐색

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;

long long ans = 1e9;
long long A, B;

void dfs(long long val, long long cnt)
{
	if (val > B ||cnt>=ans)
		return;

	if (val == B)
	{
		ans = min(cnt + 1, ans);
		return;
	}

	dfs(val * 2, cnt + 1);
	dfs(val * 10 + 1, cnt + 1);

	return;
}

int main()
{
    ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> A >> B;
	dfs(A,0);

	if (ans == 1e9)
		ans = -1;

	cout << ans;
    
	return 0;
}