[백준 알고리즘/C++/그리디] 16953 A→B

 

 

정수 A에 2를 곱하거나, 가장 오른쪽에 1을 추가하여 정수 B를 만들 수 있다

몇 번의 연산으로 만들 수 있는지 구하는 문제

 

 

A에서 B를 만들지말고 B에서 A를 만들어야 할 것 같다.. A에서 B로 가려면 복잡해진다

B에서 1을 떼거나, 반으로 나눠주면 A를 찾을 수 있다

 

뭔가에 2를 곱했을 때 홀수는 나올 수 없으므로 B가 1로 끝나면 1을 떼어주고 (B/=10)

그 외의 홀수가 나왔는데 A와 같지 않다면 -1을 출력한다

짝수일 경우엔 반으로 나눠주면 된다 (B/=2)

A==B일 때 cnt를 출력하고 프로그램을 종료하면 끝

 

 

#include <iostream>
using namespace std;
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    int a, b, cnt = 1;
    cin >> a >> b;
 
    while (true) {
        if (a == b) {
            cout << cnt;
            break;
        }
 
        if (a > b) {
            cout << -1;
            break;
        }
 
        if (b % 10 == 1) b /= 10;
        else if (b % 2 == 0) b /= 2;
        else {
            cout << -1;
            break;
        }
 
        cnt++;
    }
}

 

코드의 else 부분을 까먹어서 틀렸었다..

A에 2를 곱했을 때 홀수가 나올 수 없다는 생각에 갇혀

B를 2로 나누었을 때 홀수 나올 수 있는건 생각 못함ㅎ

어이없어..