[BOJ 16953번/C++] A → B

미숙한 블로그 주인이 코딩테스트 문제를 풀어가는 과정을 담은 글입니다. 이 풀이가 효율적인 풀이가 아닐 수 있으며, 부정확한 정보가 많이 있을 수 있습니다. 보완해야할 점이 있다면 댓글로 남겨주세요!

 

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

16953번: A → B

A → B

풀이

이 문제는 탐욕법으로 풀 수 있었다.

 

문제에서 가능하다고 한 연산을 반대로 생각해서 풀었더니 곧바로 답이 돌출됐다.

 

1. A에서 2를 곱한다. → B에서 2를 나눈다.

2. A의 가장 오른쪽에 1을 추가한다. → B에서 가장 오른쪽에 있는 1을 빼준다.

 

1의 연산을 할 수 없을 때, 2의 연산도 할 수 없다면 A를 B로 바꿀 수 없다는 뜻이다.

위 과정을 모두 진행하고 나서도 A와 B가 같지 않은 경우가 생길 수 있다. 이 경우도 A를 B로 바꿀 수 없다는 뜻이다.

 

문제 풀이는 위에서 쓴 내용을 그대로 반영해주면 된다.

1. B가 짝수이면 2로 나누어주고 

2. B가 홀수이면 끝자리가 1인지를 확인해주고 빼준다. 만약 그렇지 않다면 -1을 반환한다.

3. 반복문이 끝났을 때 A 와 B가 같다면 횟수를 출력한다. 그렇지 않으면 -1을 출력한다.

 

이때, 문제에서 마지막에 연산 횟수에 +1을 하라고 되어있으니 유의하자.

 

#include <iostream>

#define endl '\n'

using namespace std;

int main() {
    cin.tie(NULL);
    ios::sync_with_stdio(false);

    int A, B;
    cin >> A >> B;

    int count = 0;
    while (A < B) {
        if (B % 2 == 0) {
            B /= 2;
            count++;
        }
        else {
            int tmp = B / 10;
            tmp = B - (tmp * 10);
            if (tmp == 1) {
                B /= 10;
                count++;
            }
            else {
                count = -2;
                break;
            }
        }
    }
    if (A > B)
        count = -2;
    
    cout << count + 1 << endl;

    return 0;
}