14395번_4연산

문제 출처 : https://www.acmicpc.net/problem/14395

14395번: 4연산

1) 10억이 넘는 배열은 못 만듦 -> set, map을 활용한다

2) bfs을 해준다.

<c++>

 

#include<iostream>
#include<set>
#include<queue>
#include<map>
#include<algorithm>
#define MAX 1000000001
using namespace std;
set<long long > se;
map<long long,char > ma;
map<long long,long long > t;
string temp;
int main(void)
{
    long long  n,m;
    cin>>n>>m;
    if(n==m)
    {
        cout<<0<<endl;
        return 0;
    }
    queue<pair<long long ,long long > > q;    
    q.push({n,0});
    se.insert(n);
//    set<long long > ::iterator iter;
    
    while(!q.empty())
    {
        long long x=q.front().first;
        long long cnt=q.front().second;
        q.pop();
        if(x==m)
        {
        //    cout<<cnt<<endl;
            temp+=ma[x];
            int s=t[x];
            while(cnt--!=1)
            {
                temp+=ma[s];
                s=t[s];
                
            }
            reverse(temp.begin(),temp.end());
            cout<<temp<<endl;
        }
        long long next=x*x;
        if(next<=1000000000&&se.find(next)==se.end())
        {
            se.insert(next);
            q.push({next,cnt+1});
            ma[next]='*';
            t[next]=x;
            
        }
        next=x+x;
        if(next<=1000000000&&se.find(next)==se.end())
        {
            se.insert(next);
            q.push({next,cnt+1});
                ma[next]='+';
                        t[next]=x;
        }
        next=x-x;
        if(next>=1&&se.find(next)==se.end())
        {
            se.insert(next);
            q.push({next,cnt+1});
                ma[next]='-';
                        t[next]=x;
        }
        next=x/x;
        if(next>=1&&se.find(next)==se.end())
        {
            se.insert(next);
            q.push({next,cnt+1});
                ma[next]='/';
                        t[next]=x;
        }
    }
    if(se.find(m)==se.end())
    {
        cout<<-1<<endl;
    }
    
    
    return 0;
    
}