[백준 16953][C++] A → B

문제 링크

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

---

◆문제 해결 및 설명◆

A에 할 수 있는 연산은 A *= 2 와 A = A*10+1 이 있다.

 A *= 2 혹은  A = A*10+1 두개에서 하나를 골라서 연산을 할경우의 시간 복잡도는 O(2^n)이다.

제일 낮은 수치 증가 식인 A *= 2 만 한다고 하고 A가 가장 낮은 1인값, 최대 10의9승(B의 최댓값) 보다 낮되 가장 큰값이 되기 위한 연산 횟수는 최대 30번이다. 따라서 최대 연산 깊이는 30이다. 따라서 완전 탐색으로 풀어보았다.

◆코드 전문◆

#include <iostream>

using namespace std;
long A, B, answer = -1;

void cal(long buf, int depth)
{
    if (buf == B)
    {
        answer = depth;
    }
    else if (buf > B)
    {
        return;
    }
    cal(buf * 2, depth + 1);
    cal(buf * 10 + 1, depth + 1);

    return;
}

int main()
{
    cin >> A >> B;
    cal(A, 1);
    cout << answer;
}