[BOJ] 백준 16953 A → B c++ 코드 / 풀이

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

16953번: A → B

문제해설

 

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

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

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

간단하게 A에 2를 곱하거나 1을 붙이는 과정을 반복해서 B를 만들 때 필요한 연산의 최솟값을 구하면 됨

 

문제풀이

 

A x 2 or A*10+1을 반복해서 B를 만들고 이 과정에서 연산의 최솟값을 구하는 것

위 그림처럼 A가 2일 때 2를 곱하거나 뒤에 1을 붙이는 과정을 계속 반복(BFS로)

만들 수 없다면 -1을 출력

BFS로 연산의 결과값, 연산 횟수를 pair로 해서 BFS로 최소값을 탐색=> map<long long, int>,  map의 key가 변경된 값, value가 연산 횟수

코드설명

 

현재 수, 연산 횟수를 pair로 큐에 삽입하고 현재 수가 B와 같다면 결과값 출력

BFS가 종료될 경우 탐색하지 못한 것이므로 -1 출력

 

코드

 

#include <bits/stdc++.h>

using namespace std;

/*
    1. 2를 곱한다
    2. 10을 곱하고 1을 더한다
    map<int, int>, tmp는 long long
    key가 변경된 값, value가 연산 횟수
    1,000,000,000을 초과하면 -1 출력
*/

int arr[2][100001];
int dp[2][100001];

int main(void){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    long long a, b;

    cin >> a >> b;
    int cnt = 1;
    queue<pair<long long, int>> v;
    v.push({a*2, cnt});
    v.push({(a*10)+1, cnt});

    while(!v.empty()){
        pair<long long, int> p = v.front(); v.pop();
        if(p.first == b){
            cout << p.second+1;
            return 0;
        }
        else if(p.first > INT_MAX) continue;
        else {
            
            long long one = p.first * 2;
            long long two = (p.first * 10) + 1;
            if(one < INT_MAX){
                v.push({one, p.second+1});
            }
            if(two < INT_MAX){
                v.push({two, p.second+1});
            }
        }
    }

    cout << -1;

}