A->B

A에서 B까지 다음의 연산을 사용할 때, 연산의 최소 횟수를 구하시오.

 

1. 2를 곱한다.

2. 1을 오른쪽에 붙여준다.

 

그런데 잘 생각해보면 B에서 A로 내려올 때 1번 연산과 2번 연산은 양립하지 않는다. 즉, 거꾸로 B에서 A로 내려올 때 2로 나눠주고, 1을 떼어 주는 일은 동시에 일어나지 않는다. 따라서, 모든 수에서 연산 횟수는 항상 최소 횟수로 구해짐을 알 수 있다.

 

+ substr함수를 사용 할 때는 새로운 string 을 선언한 뒤 substring을 그곳에 할당해 주어야 한다.

#include <iostream>
#include <string>
using namespace std;
int A,B,ans=1;
int main() {
	cin>>A>>B;
	while(B!=A){
		ans++;
		if(B%2==0&&B/2>=A) {B/=2;continue;}
		string s=to_string(B);
		if(s[s.length()-1]-'0'==1) {
			string tmp=s.substr(0,s.size()-1); //[ )
			if(stoi(tmp)>=A) {B=stoi(tmp);continue;}
		}
		ans=-1;break;
	}
	cout<<ans;
	return 0;
}