[백준] C++ 16953(A->B)

 

#include <iostream>

using namespace std;

int main(void)
{
	int num1=0;
	int num2=0;
	
	cin>>num1>>num2;
	
	int count=1;
	
	while(true)
	{
		if(num2%2==0)
		{
			num2=num2/2;
			count++;
		}
		else if(num2%10==1)
		{
			num2=num2/10;
			count++;
		}
		else
		{
			cout<<-1;
			break;
		}
		
		if(num2==num1)
		{
			cout<<count;
			break;
		}
		else if(num2<num1)
		{
			cout<<-1;
			break;
		}
	}
	
	return 0;
}

A를 B로 바꾸는 연산의 최솟값을 구하는 문제이다.

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

예제를 한번 살펴보자

 

2 162(2 → 4 → 8 → 81 → 162) 이렇게 되어있다. 총 4번의 연산을 거치고 +1을 하여 5가 답으로 출력되게 된다.

어떻게 연산의 최솟값을 구할 수 있을까??

여러 방법이 있을 수 있겠지만 나는 문제를 역으로 푸는 방법을 선택했다.

162를 2로 바꾸는 것이다.

 

내가 생각한 경우의 수는 다음과 같다

1.2로 나누어 떨어지는가??

2.일의 자리 수가 1인가??

만약 1, 2를 둘다 만족하지 못한다면 A를 B로 변환하지 못한다.(166->83->?? break)

 

만약 A와 B가 같아지게 된다면 count를 출력하고 B가 A보다 더 작아지게 된다면 이 또한 변환 불가능이기 떄문에 -1를 출력하고 while문을 빠져나오게 된다.