16953: A->B

• toc {:toc}

문제 확인하기

풀이

순방향으로 계산을 생각했을 때 1을 추가하는 기준이 명확하지 않기 때문에 역으로 B에서 A로 가는 방식을 생각했다. 2로 나눠주면서 일의 자리에 1이 나오는 경우 1을 제외해주며 연산을 카운트한다.

162 → 81 → 8 → 4 → 2

1이 아닌 홀수가 나올 경우 나눌 수 없기 때문에 해당 값을 만들 수 없으므로 -1을 출력한다. B가 A보다 작아지는 경우, A로 B를 만들 수 없다는 말과 동치이기 때문에 -1을 출력한다.

#include <bits/stdc++.h>
using namespace std;
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
 
    int a, b, res = 0;
    
    cin >> a >> b;
 
    while(true){
        if(b % 10 != 1 && b % 2 == 1){
            cout << -1 << '\n';
            exit(0);
        }
        else if(b % 10 == 1){
            res++;
            b = b / 10;
        }
        else{
            b = b / 2;
            res++;
        }
        if(a > b){
            cout << -1 << '\n';
            exit(0);
        }
        else if(a == b){
            break;
        }
    }
 
    cout << res+1 << '\n';
 
    return 0;
}