[백준] 16953 A->B c++

 

문제 링크 https://www.acmicpc.net/problem/16953

KEY

• 일반 구현으로도 문제풀이가 가능하나, DFS를 이용할 때 더 쉽게 접근할 수 있다.
• 2를 곱하거나, 뒤에 1을 붙이는 경우 총 2가지경우를 모두 탐색한다.
• 자료형을 주의깊게 보자..

Code

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
long long A, B;
int result = 999999999;
void dfs(long long x, int cnt) {
    if (x > B)
        return;
    if (x == B) {
        result = min(result, cnt);
        return;
    }
 
    dfs(x * 2, cnt + 1); //2를 곱한다.
    dfs(x * 10 + 1, cnt + 1); //1을 수의 가장 오른쪽에 추가한다.
}
 
int main() {
    cin >> A >> B;
    dfs(A,0);
    if (result == 999999999)
        cout << -1;
    else
        cout << result + 1;
}