BOJ 16953 A -> B

다음 두가지 조건을 역으로 계산 하여 B 에서 A로 만들수 있는지 없는지 찾아가면 된다.

 

이때 중요한점은 B가 홀수 인지 짝수 인지 판단하고, 홀수일경우 일의 자리가 1 인지 아닌지 확인하고 1이 아닐경우 A를 절때 만들 수 없다는 것을 찾아내면 된다. 만약 B가 짝수라면 2로 계속 나눠준면된다.

 

위의 조건을 적용하여 새로 만들어진 B`이 A보다 작아진경우 반복문을 멈추고 A와 B`이 같을경우 결과에 1을 더해준다.

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

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

	int a, b;

	cin >> a >> b;

	int result = 0;
	while(b > a)
	{
		if(b % 2 == 1)
		{
			string s = to_string(b);
			if(s[s.size() - 1] == '1')
			{
				s = s.substr(0, s.size() - 1);
				b = stoi(s);
				result++;
				if(b < a)
				{
					result = -1;
					break;
				}
				else
				{
					continue;
				}
			}
			else
			{
				result = -1;
				break;
			}
		}
		else
		{
			b /= 2;
			result++;
			if(b < a)
			{
				result = -1;
				break;
			}
		}
	}

	if(a == b)
	{
		result++;
	}
	
	cout << result;
}

또 다른 풀이는 A를 기준으로 조건(A*2 또는 A의 가장 오른쪽에 1을 추가)을 적용하여 A==B일때 까지 찾아가고 A > B 일 경우 만들수 없음을 표시해준다. 

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

const long long imp = -987654321;

int go(long long a, long long b) {
  if (a == b) return 1;
  if (a > b) return imp;
  return max(go(a*2, b) + 1, go(a*10+1, b) + 1);
}

int main() {
  long long a, b;
  cin >> a >> b;
  int ans = go(a, b);
  if (ans < 0) {
    cout << -1 << '\n';
  } else {
    cout << ans << '\n';
  }
  return 0;
}