Codeforces #1485A Add and Divide

문제

https://codeforces.com/problemset/problem/1485/A

걸린 시간

00 : 14 : 03

풀이

C++

#include <bits/stdc++.h>
#define INF 1e9
#define all(c) c.begin(), c.end()
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

int solve(){
    int a, b;
    cin >> a >> b;
    queue<pair<int, int>> q;
    map<pair<int, int>, int> visited;
    q.push(make_pair(a, b));
    visited[make_pair(a, b)] = 1;
    int op = 0;
    while(!q.empty()){
        int size = q.size();
        for(int i = 0; i < size; i++){
            a = q.front().first;
            b = q.front().second;
            q.pop();
            if(a == 0) return op;
            if(!visited[make_pair(a/b, b)]){
                q.push(make_pair(a/b, b));
                visited[make_pair(a/b, b)] = 1;
            }
            if(!visited[make_pair(a, b+1)]){
                q.push(make_pair(a, b+1));
                visited[make_pair(a, b+1)] = 1;
            }
        }
        op++;
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int tc;
    cin >> tc;
    while(tc--){
        cout << solve() << "\n";
    }
    return 0;
}

양의 정수 a, b 가 주어진다. a 를 b 로 나누고 하한, b 의 값을 1 증가 두 가지 연산이 있는데 a 값이 0 이 되도록 하는 연산의 최소 수를 구해야 한다.

모든 경우의 수를 중복없이 시도하면서 연산의 최소값을 찾는 문제이므로 bfs 를 사용하면 해결할 수 있다.