[BOJ/Gold 4] 백준 31804 Chance!(C++)

문제 링크

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

 

문제

자료구조 시험에서 우찬이는 a점을 받았고, 상훈이는 우찬이보다 높은 b점을 받았다. 우찬이는 상훈이보다 점수가 낮아서 화가 났지만, 공부를 하나도 하지 않아서 상훈이보다 시험을 잘 볼 수는 없다는 것을 알고 있었다. 하지만 우찬이는 최소한 동점을 받고 싶었기 때문에, 자신의 수를 바꾸는 마법을 배워서 다음 3가지 마법을 사용할 수 있게 되었다.

 

1. 물 주기: 수에 물을 주면 수가 1 커진다.
2. 밥 주기: 수에 밥을 주면 수가 2배가 된다.
3. chance!: 수에 chance!를 외치면 수가 10배가 된다.

하지만 chance!를 외치면 목이 너무 아프기 때문에 우찬이는 chance! 마법을 최대 한 번만 사용할 수 있다. 그리고 마법을 사용할 때마다 팔을 이리저리 휘저어야해서 힘이 많이 들기 때문에 마법을 최소한으로 사용하고자 한다. 우찬이가 상훈이와 동점이 되도록 하려고 할 때 마법을 최소한으로 사용하도록 도와주자.

 

입력

첫 번째 줄에 우찬이와 상훈이의 점수 a와 b가 공백으로 구분되어 주어진다.

 

출력

첫 번째 줄에 a를 b로 만들기 위해 필요한 최소 마법 사용 횟수를 출력한다.

 

제한

•  1 ≤ a < b ≤ 1,000,000
•  a와 b는 정수이다.

 

예제 입력 1

30 70

예제 출력 1

6

예제 입력 2

1 1024

예제 출력 2

10

예제 입력 3

3 30000

예제 출력 3

17

 

알고리즘 분류

• 그래프 탐색

 

풀이

chance! 마법을 사용하기 전일 때와 사용할 때를 구분해서 어떤 숫자를 방문했는지를 기록해야 한다.

A를 B로 만들어야 하므로, B를 넘어서면 안 되기 때문에 A가 증가할 수 있는 수를 B까지로 한정한다.

그리고 물 주기, 밥 주기, chance! 마법을 각각 사용하며 증가하는 수를 탐색한다.

chance! 마법을 사용한 이후부터는 chance! 마법을 다시 사용할 수 없다.

 

코드

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#define MAX 1000001
#define INF 2e9
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
int A, B;
bool Visited[MAX][2];
int Answer = INF;

void input() {
    cin >> A >> B;
}

void bfs() {
    queue<pair<pair<int, int>, bool> > Q;
    Q.push(make_pair(make_pair(A, 0), false));
    Visited[A][0] = true;

    while (!Q.empty()) {
        int NowS = Q.front().first.first;
        int NowM = Q.front().first.second;
        bool isChanceUsed = Q.front().second;
        Q.pop();

        if (NowS == B) {
            Answer = min(Answer, NowM);
            continue;
        }

        if ((NowS + 1 <= B) && !Visited[NowS + 1][isChanceUsed]) {
            Q.push(make_pair(make_pair(NowS + 1, NowM + 1), isChanceUsed));
            Visited[NowS + 1][isChanceUsed] = true;
        }
        if ((NowS * 2 <= B) && !Visited[NowS * 2][isChanceUsed]) {
            Q.push(make_pair(make_pair(NowS * 2, NowM + 1), isChanceUsed));
            Visited[NowS * 2][isChanceUsed] = true;
        }
        if (!isChanceUsed && (NowS * 10 <= B) && !Visited[NowS * 10][isChanceUsed]) {
            Q.push(make_pair(make_pair(NowS * 10, NowM + 1), true));
            Visited[NowS * 10][isChanceUsed] = true;
        }
    };
}

void settings() {
    bfs();
}

void find_Answer() {
    cout << Answer << "\n";
}

int main() {
    FASTIO
    input();
    settings();
    find_Answer();

    return 0;
}