[백준/C++] 16953번: A -> B

문제

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

16953번: A → B

---

문제 요약

정수 A와 B를 입력 받고, A를 B로 바꾸는데 필요한 연산의 최솟값에 1을 더한 값을 출력한다.

 

< 가능 연산 >

1. 2를 곱한다.

2. 1을 수의 가장 오른쪽에 추가한다.

---

코드

#include <iostream>
#include <algorithm>

#define ll long long

using namespace std;

ll a, b;
ll res = 1e9;

void dfs(ll x, ll cnt) {
    // a가 연산을 거쳐서 b가 되었다면
    if (x == b) {
        res = min(res, cnt); // 최소 연산 횟수 갱신
        return;
    }

    // 연산은 x를 증가시키는 연산만 존재하므로 b를 넘어가면 x는 더이상 b가 될 수 없으므로 종료
    if (x > b) {
        return;
    }

    // 가능한 연산의 경우의 수를 dfs 탐색

    // 1번 연산을 하는 경우 탐색
    ll y = 2 * x;
    dfs(y, cnt + 1);

    // 2번 연산을 하는 경우 탐색
    y = x * 10 + 1;
    dfs(y, cnt + 1);
}

int main() {
    
    cin >> a >> b;

    dfs(a, 1);

    // res가 초기 값이라면, 가능한 경우의 수가 없으므로 -1 출력
    if (res == 1e9) {
        cout << -1;
    }
    else {
        cout << res;
    }

    return 0;
}

---

코드 설명

1. A와 B를 입력 받는다.

 

2. A값에서 시작하여 DFS 탐색을 시작한다.

 

3. 탐색을 하다 A값이 B가 되는 경우의 수를 발견하면, 그 때의 연산 횟수와 지금까지 발견된 최소 연산 횟수를 비교하여 갱신한다.

 

4. 2가지 연산 모두 A를 증가시키는 연산이므로, 만약 A가 B를 넘어가버린다면, A는 B가 될 수 없으므로 해당 경우의 수 탐색을 종료한다.

 

5. 모든 탐색이 종료된 후에도 res값이 초기값 그대로라면, 가능한 경우의 수가 없다는 의미이므로 -1을 출력하고, 그렇지 않다면 res값을 출력한다.

(res의 초기값은 1,000,000,000)

 

추가적으로, A는 1, B는 1,000,000,000인 최악의 경우에서 스택오버플로우 에러가 발생하기 때문에, long long 형으로 변수를 선언해주는 것이 좋다.