[그리디 #14] BOJ 16953 - A -> B

 

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

16953번: A → B

 

접근 방법

처음엔 a를 기준으로 다음과 같이 해결했다.

 

i) if(a*10+1  <= b) { a에 a*10+1 }

ii) else { a = a * 2 }

 

여기서 틀린 점을 생각해보면 

마지막에 1을 붙일 수 있으면 붙이기 때문에, ㅁ --(*2)--> ㅁ --(*2)-->ㅁ 인 경우에 정답을 피해갈 수 있다.

 

여기서 착안한 것이 b를 기준으로 해보자는 것.

 

b를 기준으로 끝이 1이면 띄어 버리면 된다.

 

근데 여기서도 문제가 존재한다.

 

예를 들어 11 33을 보자.

정답은 당연히 -1이다.

그러나 33/2를 하면 소수부분이 날라가기 때문에, 2로 나누어 떨어질때만 /2 를 하도록 설정

 

정리하자면.

1) if(b%10 == 1) { b/=10 }
2) else if(b%2 == 0) { b/=2 }
3) else { break }

 

 

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <deque>
#include <string>

using namespace std;

string ca, cb;
long long a, b;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> a >> b;

	long long cnt = 0;
	while (b > a) {
		if (b % 10 == 1) {
			//cout << "a: " << a << " , b: " << b << endl;
			b /= 10;

		}
		else if (b % 2 == 0) {
			b /= 2;
		}
		else {
			//cout << "a: " << a << " , b: " << b << endl;
			break;
		}
		cnt++;
	}

	if (a == b) {
		cout << cnt + 1;
	}
	else {
		cout << -1;
	}
}