[14395] 4연산

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

14395번: 4연산

<문제>

먼저,  '-'연산은 전혀 의미가없다. 수행하면 0이되는데 0에서 다른 정점으로 갈 방법이 없고, 종료정점은 1 이상이다.

1e9만큼 bool형을 만들순 없지만, 가능한 정점의 폭에 비해 방문하는 정점의 개수가 꽤 작다.

set을 사용하여 방문처리를 진행해주고, 10억*10억>INT_MAX이므로 일시적으로 long long을 사용해준다.

 

<소스코드>

#include <bits/stdc++.h>
using namespace std;
const int MAX = 1e9;
typedef long long ll;
typedef struct {
    ll n;
    string op;
} state;
queue<state> q;
set<ll> s;
ll x, y;
int main(void) {
    cin >> x >> y;
    if (x == y) {
        cout << 0;
        return 0;
    }
    q.push({x, ""});
    s.insert(x);
    while (!q.empty()) {
        auto cur = q.front();
        q.pop();
        if (cur.n == y) {
            cout << cur.op;
            return 0;
        }
        ll temp = cur.n;
        if (temp * temp <= MAX) {
            ll next = temp * temp;
            if (s.find(next) == s.end()) {
                s.insert(next);
                q.push({next, cur.op + "*"});
            }
        }
        if (temp + temp <= MAX) {
            ll next = temp + temp;
            if (s.find(next) == s.end()) {
                s.insert(next);
                q.push({next, cur.op + "+"});
            }
        }
        if (s.find(1) == s.end()) {
            s.insert(1);
            q.push({1, cur.op + "/"});
        }
    }
    cout << -1;
    return 0;
}