[SWEA] 7559. A -> B

SWEA - ‘7559. A -> B’ 알고리즘 문제 풀이

분류

문제 링크 : https://swexpertacademy.com/main/code/userProblem/userProblemDetail.do?contestProbId=AWo3PPBaSecDFAQi

풀이

정수 A, B가 입력으로 주어질 때, A를 B로 만들기 위해서 필요한 최소 연산 횟수를 출력하는 문제이다.

• 문제 페이지에 109라고 되어있는데, 제곱수의 오타인것 같다.
• 정확한 범위는 이다.

다음과 같이 두 가지 연산이 있다.

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

A를 B로 바꾸는데 필요한 연산의 최솟값에 1을 더한 값을 출력하고 만들 수 없는 경우에는 -1을 출력한다.

---

K번째 연산을 통해 만들 수 있는 수가 B인지 확인하면 되므로, (값, 필요한 연산 횟수) 형태의 자료형을 선언하고 만들 수 있는 수의 경우의 수에 대하여 너비 우선 탐색을 하면 된다.

주의할 점으로는,

1 1000000000 가 입력으로 들어오면, n.first에 10을 곱하는 과정에서 정수 오버플로가 발생하여 음수가 되는 문제가 발생했다. (음수에 대해 1, 2 연산을 반복하니 결국 무한 루프에 빠진다.)

따라서 오버플로를 해결하기 위해, 곱하는 수를 더 큰 범위를 갖는 자료형으로 바꾸어도 되고, int 타입을 사용하겠다면 n.first가 10^8 이하인 경우에만 10을 곱하고 1을 더하는 연산을 수행하도록 처리하면 된다.

아래 코드에서는 long long을 사용했다.

소스 코드

#include <iostream>
#include <queue>
using namespace std;

typedef long long LL;
typedef pair<LL, int> pii;

int T;

// 10을 곱하는 과정에서 오버플로가 발생할 수 있음.
long long A, B;

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

    cin >> T;
    for (int tc = 1; tc <= T; ++tc) {
        cin >> A >> B; // A == B를 만족하는 입력은 주어지지 않는다.
        int ans = 0;

        queue<pii> q;
        q.push(make_pair(A, 0));
        while (!q.empty()) {
            pii& n = q.front();

            if (2 * n.first == B || n.first * 10 + 1 == B) {
                ans = n.second + 1;
                break;
            }
            if (2 * n.first <= B) {
                q.push(make_pair(2 * n.first, n.second + 1));
            }

            // n.first가 int type일 때, 10을 곱하는 과정에서 오버플로가 발생할 수 있음.
            if (n.first * 10 + 1 <= B) {
                q.push(make_pair(n.first * 10 + 1, n.second + 1));
            }
            q.pop();
        }

        // 만들 수 없음.
        if (ans == 0) {
            cout << "#" << tc << " -1\n";
        }
        else {
            cout << "#" << tc << " " << ans + 1 << "\n";
        }

    }

    return 0;
}