[ boj : 14395 ] 4연산

www.acmicpc.net/problem/14395

14395번: 4연산

문제 : 사칙연산을 해서 s->t 로 만들 수 있을때 연산동작을 출력하여라, 이때 사전순으로 앞서있는 문자열을 먼저 출력

 

해설 : 간단하게 dfs나 bfs를 사용해서 풀면 됩니다. 다만 이제 범위가 n이 10억인걸 유의해야겠죠.

이미 방문을 하였는지 체크하기 위해선 단순 배열로는 무리라는 것을 알 수 있습니다. 메모리가 감당이 안되기 때문이죠

그럼 우린 다른 방법을 택해야 되는데 자료구조 중에 set 이나 map을 사용하면 됩니다.

 

그 후 정답이 될 후보를 벡터에 담아준 다음에 연산자 오버로딩을 통해 정렬해주어 출력해주면 되겠죠.

언제나 오버플로는 중요!!!

 

#include <iostream>
#include<vector>
#include<queue>
#include<string>
#include<set>
#include<algorithm>

using namespace std;
using ll = long long;

struct info{
	ll num;
	string str;
	bool operator<(const info &cur) const{
		return str<cur.str;
	}
};
ll s,t;
set<ll> st;
vector<string> ans;
int main() {
	// your code goes here
	cin>>s>>t;
	if(s==t){
		cout<<0;
		return 0;
	}
	queue<info> q;
	q.push({s,""});
	st.insert(s);
	
	while(!q.empty())
	{
		info cur = q.front();
		q.pop();
		
		if(cur.num==t){
			ans.push_back(cur.str);
			continue;
		}
		
		if(st.find(cur.num*cur.num)==st.end()){
			st.insert(cur.num*cur.num);
			q.push({cur.num*cur.num,cur.str+'*'});
		}
		if(st.find(cur.num*2)==st.end()){
			st.insert(cur.num*2);
			q.push({cur.num*2,cur.str+'+'});
		}
		if(st.find(0)==st.end()){
			st.insert(0);
			q.push({0,cur.str+'-'});
		}
		if(cur.num!=0 && st.find(1)==st.end()){
			st.insert(1);
			q.push({1,cur.str+'/'});
		}
	}
	if(ans.size()==0)
		cout<<-1;
	else{
		sort(ans.begin(),ans.end());
		cout<<ans[0];
	}
	return 0;
}