백준 16953 A → B

 

큐에 b보다 작은 연산결과들을 연산의 횟수와 같이 집어넣고 

연산으로 b를 만들었다면 그 횟수를 출력하는 방식으로 구현하였다.

 

#include <iostream>
#include <queue>

#define INF 987654321

using namespace std;



int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    long long a, b;


    cin >> a >> b;



    queue<pair<long long, int>> q;        //first: 해당 숫자, second: 연산의 수에 1을 더한 것

    q.push({a, 1});


    while (!q.empty()) {

        long long cur = q.front().first;
        int cnt = q.front().second;

        q.pop();

        if (cur == b) {
            cout << cnt;
            return 0;
        }




        //1번 연산
        if (cur * 2 <= b) {

            q.push({cur * 2, cnt + 1});
        }

        //2번 연산
        if (cur * 10 + 1 <= b) {

            q.push({cur * 10 + 1, cnt + 1});

        }





    }

    cout << -1;




    return 0;
}

 

 

근데 본인은 이런 식으로 문제를 풀기 위해 이 문제를 건드린 것이 아니다. 

그리디 알고리즘이 개인적으로 약하다고 생각해서 이 문제를 골랐던 것이다.

그래서 이 문제를 다시 한번 더 풀어보았다.

 

#include <iostream>
#include <queue>

#define INF 987654321

using namespace std;

//Greedy

int main(){


    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int a, b;

    cin >> a >> b;

    int ans = 1;

    int cur = b;

    while (cur >= a) {
        if (cur == a) {
            cout << ans;
            return 0;
        }

        //해당 값이 짝수라면->1번 연산으로만 해당 값을 만들 수 있음
        if (cur % 2 == 0) {
            cur /= 2;
            ans++;
        }
        //끝의 자리가 1이라면->2번 연산으로 해당 값을 만들 수 있음
        else if (cur % 10 == 1) {
            cur = (cur - 1) / 10;
            ans++;
        }
            //이외의 경우->어떤 연산을 해도 cur을 만들 수 없음
        else {
            cout << -1;
            return 0;
        }
    }

    cout << -1;
    return 0;


}

 

bfs와 반대의 방식으로 b에서 a를 찾아가는 방식이다.

이전에 어떤 연산을 하여 해당 값을 찾는지 확인하는 방식이다.

 

162->81(1번 연산으로만 만들 수 있음)

 

81->8(8에서 2번 연산으로만 만들 수 있음)

 

8->4(1번 연산으로만 만들 수 있음)

 

4->2(1번 연산으로만 만들 수 있음)

 

 

즉 a에서 b로 만들 수 있는 방법의 순서는 한 가지밖에 존재하지 않는다.

이를 이용하여 연산의 수를 계산할 수 있다.