C++ 백준 16953번 : A → B

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

16953번: A → B

문제

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

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

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

입력

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

출력

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

---

풀이

비슷한 문제를 풀어본거 같은데 ,, A -> B 를 만드는 것보다 B -> A 를 만든다고 생각하면 쉽다.

B에서 2로 나눠지거나 마지막 숫자가 1인 경우에만 연산을 한다. 마지막 숫자가 1인 아닌 홀수인 경우와 B가 A보다 작아지면 연산을 할 수 없다고 판단한다. 여기서 마지막 숫자가 1인지 판단하는 것은 string으로 바꾼 후에 판단했다~

---

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
int dp[2][100001] = { 0 }; // 0 : 2원, 1: 5원
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int num, cnt;
	cin >> num >> cnt;

	int ans = 1; // +1 조건 적용
	
	while (true) {
		if (num == cnt) { // 같아지는 경우 종료
			cout << ans << "\n";
			return 0;
		}
		else if (num > cnt) { // 만들 수 없는 경우
			cout << -1 << "\n";
			return 0;
		}
		
		// 연산
		if (cnt % 2 == 0) {
			cnt = cnt/ 2;
		}
		else {
			string tmp = to_string(cnt); // int to string
			if (tmp[tmp.size() - 1] == '1') { // 마지막이 1이면 
				tmp.pop_back(); // 삭제 후 
				cnt = stoi(tmp); // ans에 저장
			}
			else { // 2로도 안 나눠지고 1이 아닐 시 --> 만들 수 없는 경우
				cout << -1 << "\n";
				return 0;
			}
		}
		ans++; 

	}
}

dp문제나 그리디 문제 같았는데 알고리즘 분류보니 bfs문제 ,,,? 어떻게 접근하는 거죠 ..? 주말에 찾아보는 걸로!