[백준][C++] 16953번: A → B <205>

직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다.

16953번: A → B

생각의 흐름

이번 문제는 예전에 비슷한 문제를 푼 경험이 있어 금방 해결하였다.

역으로 해결해 나가면 된다!

 

예를 들어 다음과 같은 예시가 있다고 해보자

2 162

이를 역으로 162 -> 81 -> 8 -> 4 -> 2 가 될수 있다. B부터 시작하여 A를 만들어 간다고 생각하면 편하다.

 

B에서 마지막 숫자가 1로 끝나면 => 기존 A의 수에 1추가 연산으로 B가 된것

B에서 마지막 숫자가 1이 아니고, 2로 나누어 떨어지는 경우 => 기존 A의 수에 2배를 하여 B가 된것

 

위 점을 명심하면서 역으로 계산하면 된다.

 

2. 나의 코드

#include <bits/stdc++.h>
using namespace std;
int A, B;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> A >> B;

    int cnt = 0;
    while(true) {
        cnt++;
         if(A == B){
            cout << cnt;
            break;
        }else if(A > B){
            cout << -1;
            break;
        }

        if (B % 10 == 1) {
            B--;
            B /= 10;
        } else if (B % 2 == 0) {
            B /= 2;
        }else{
            cout << -1;
            break;
        }
    }

    return 0;
}