[Silver II] A → B - 16953

문제 링크

문제 링크

성능 요약

메모리: 2020 KB, 시간: 0 ms

문제 설명

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

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

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

입력

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

출력

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

코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int A; // 자연수 개수
int B; // 부분 개수

int ans = 21e8;

void solve(int cur, int opCnt) {
	// 조건 달성
	if (cur == A) {
		ans = min(opCnt + 1, ans);
	}

	// 최소값보다 크면 종료
	if (cur > ans) {
		return;
	}

	// 값이 안나올때
	if (cur <= 0) {
		return;
	}

	// 마지막자리 1 제거
	if (cur % 10 == 1) {
		solve(cur / 10, opCnt + 1);
	}

	// 짝수면 2 나누기
	if (cur % 2 == 0)
		solve(cur / 2, opCnt + 1);
}

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

	// 입력
	cin >> A >> B;

	// 계산
	solve(B, 0);

	// 출력
	cout << (ans == 21e8 ? -1 : ans);

	return 0;
}