[C++] 16953번: A -> B

링크

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

16953번: A → B

문제

입출력 예제

코드

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int main(void)
{
    int answer = 1;

    string aNum, bNum;
    cin >> aNum >> bNum;

    while (stoi(aNum) < stoi(bNum))
    {
        if (bNum[bNum.size() - 1] == '1')
        {
            bNum.erase(bNum.begin() + bNum.size() - 1);
        }
        else if(stoi(bNum) % 2 == 0) 
        {
            bNum = to_string(stoi(bNum) / 2);
        }
        else
        {
            break;
        }
        
        answer++;
    }

    if (aNum == bNum)
        cout << answer << endl;
    else
        cout << "-1" << endl;

    return 0;
}

풀이

두가지 방법을 이용해서 수 A를 B로 만드는것이 목표입니다.

 

가능한 연산은 두가지 입니다.

1. A에 2를 곱하기

2. A의 맨 뒤에 1을 추가하기

 

해당 두 연산을 이용해서 A->B로 만드는 것이 아닌 B->A로 하는것이 더 간단하다고 생각했습니다.

1. B가 1로 끝난다면 맨 마지막 1을 제거하기.
2. B를 2로 나누었을 때 나머지가 0이라면 2로 나누기

 

예외사항이 있다면 13과 같이 2로 딱 나누어 떨어지지 않거나,
끝까지 연산을 했지만 A와 같아지지 않고 A보다 작아진 경우
A->B가 불가능하다고 판단하여 -1을 출력하게 됩니다.