[백준] 16953번 A->B

문제 링크: https://www.acmicpc.net/problem/16953

문제

정수 A를 B로 바꾸려고 한다. 가능한 연산은 다음과 같은 두 가지이다.

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

A를 B로 바꾸는데 필요한 연산의 최솟값을 구해보자.

입력

첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다.

출력

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

문제 이해

dfs문제로 a와 b의 입력을 받으면 a가 b로 되게 만들어야 되는데,
여기서 사용하는 연산은 두가지이다.
현재 수에 2를 곱하는 것과 현재 수에 10을 곱한후 1를 더하는 연산 두가지이다.
BFS를 통해 level별로 진행하다 b랑 동일 한 수가 나오면, 멈추고 더 큰 수가 나오면 queue에 넣지 않고, 작은 수가 나오면 queue에 넣는 방식으로 구현을 한다.

문제 접근

1. 입력
2. BFS를 진행.
3. 2번 진행 중 동일 한 수가 나오면 해당 level을 return 해줌.

코드 구현(c++)

#include <iostream>
#include <queue>

using namespace std;

queue<pair<long,int> >q;
long long target;
long long A;
int BFS(){
    while(!q.empty()){
        long long num = q.front().first; int cnt = q.front().second;
        q.pop();
        if(num == target) return cnt;
        long long newNum1, newNum2;
        newNum1 = num*2;
        newNum2 = num*10 + 1;
        if(newNum1 <= target) q.push(make_pair(newNum1, cnt+1));
        if(newNum2 <= target) q.push(make_pair(newNum2, cnt+1));
    }
    return -1;
}

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

    cin >> A >> target;
    q.push(make_pair(A,1));
    cout << BFS() << "\n";
}

평가

타입을 잘못 설정하여서 여러 번 틀렸다.
int : -2,147,483,648~ 2,147,483,647
long : -2,147,483,648~ 2,147,483,647
long long : -9,223,372,036,854,775,808~
9,223,372,036,854,775,807