BOJ) 14395 - 4연산

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

14395번: 4연산

처음 풀이할 때 while 문 안에 연산을 줄이려고 queue에 s랑 1 (s/s)을 넣고 시작했는데...

'/' 연산은 사전순으로 마지막이기 때문에 이렇게 하면 결과가 달라지게 됩니다..!

 

어떤 수라도 '-'연산을 하면  실행하면 0이 됩니다. 0은 다른 연산  ('*','+')을 수행해도 값이 바뀌지않고, s와 t의 범위가 1 이상이기에 연산에서 제외했습니다.

또, 어떤 수라도 '/'연산 후 1이되기에 최초 한번만 수행합니다.

---

C++ 소스  코드

#include <iostream>
#include <string>
#include <set>
#include <queue>
using namespace std;
int main(){
    long long s,t;
    cin >> s >> t;
    if (s  == t){
        cout << 0 <<'\n';
        return 0;
    }
    set<long long> st;
    st.insert(s);
    queue<pair<long long , string> > q;
    q.push(make_pair(s,""));
    bool ck = true;
    while(!q.empty()){
        long long num = q.front().first;
        string str = q.front().second;
        q.pop();
        if (num == t) {
            cout << str << '\n';
            return 0;
        }
        long long tmp =num*num;
        if (tmp <= t && st.find(tmp) == st.end()){
            st.insert(tmp);
            q.push(make_pair(tmp,str+'*'));
        }
        tmp = num*2;
        if (tmp <= t && st.find(tmp) == st.end()){
            st.insert(tmp);
            q.push(make_pair(tmp,str+'+'));
        }
        if (ck){
            st.insert(1);
            q.push(make_pair(1,str+'/'));
            ck = false;
        }
    }
    cout << -1 << '\n';
    return 0;
}