[Baekjoon] 백준 16953번: A → B (c++)

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

16953번: A → B

 

A → B 로 갈때, A는 곱하기 2를 하는 방법과, 마지막 자리에 1를 붙이는 방법이 있다.

A를 기준으로 B를 만들면, 곱하기2를 하는방법과 뒤에 1를 붙이는 방법으로 가지수가 나누어져서 최솟값을 구하기 위해서는 많은 경우를 생각해야 하기 때문에, B를 기준으로 A를 만드는 방법으로 진행했다.

 

1. B의 끝자리가 1이면, 끝자리 1을 제거함

2. 끝자리가 1이 아닌 짝수라면, B/2를 B에다가 저장함

3. 1번이나 2번 중 하나가 실행되었을 때, cnt++로 횟수를 세줌

4. 1~3번을 A == B일때까지 반복 후 cnt 출력

 

** A는 뒤에 1을붙이거나, 곱하기2를 하므로 1을 제외한 홀수는 만들어 질 수 없기 때문에 1을제외한 홀수가 나오면 B -> A를 만들수 없다. 그러므로 -1 출력

** B를 A로 만들 수 없는 경우, (A != 1  && B == "1") -1 출력

 

 

 

---

#include <string>
#include <vector>
#include <iostream>
using namespace std;

int main(){
//    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    string A,B;
    cin >> A >> B;
    
    //A를 B로 만드는 것. A < B
    int cnt = 0;
    while (A != B) {
        if(A != "1" && B == "1") { cnt = -2; break;}
        if(B.back() == '1') B.erase(B.end()-1);
        else {
            if(stoi(B) % 2 == 0){
                int b = stoi(B) / 2;
                B = to_string(b);
            } else { cnt = -2; break;}
        }
        cnt++;
    }
    
    cout << cnt+1;
    return 0;
}