14395번 4연산

set에 대해 알아보자. set은 중복제거용 체크배열로 많이 쓰이는 것 같다.

set<int> s;
set<int>::iterator it;

처럼 해주면 된다. 넣을때는 insert를, 뺄 때는 erase를 사용한다.
count는 해당 인덱스가 있으면 1, 없으면 0을 반환한다.

쫌 헷갈린다. 특히 long long이 붙어야 하는 10억정도가 들어와서 더 헷갈린다.

#include <iostream>
#include <algorithm>
#include <string.h>
#include <string>
#include <queue>
#include <vector>
#include <set>
using namespace std;
const long long maxi = 1000000000;
struct Loc {
	long long x;
	string str;
	Loc(long long a, string b) {
		x = a;
		str = b;
	}
};
int main() {
	//freopen("in1.txt", "rt", stdin);
	set<long long> ch;
	long long s, t;
	cin >> s >> t;
	queue<Loc> Q;
	Q.push(Loc(s, ""));
	ch.insert(s);
	while (!Q.empty()) {
		Loc tmp = Q.front();
		Q.pop();
		//cout << tmp.str << '\n';
		if (tmp.x == t) {
			if (tmp.str.length() == 0) {
				cout << 0 << '\n';
				return 0;
			}
			else {
				cout << tmp.str << '\n';
				return 0;
			}
		}
		if (0<=tmp.x*tmp.x&&tmp.x * tmp.x <= maxi && ch.count(tmp.x * tmp.x) == 0) {
			ch.insert(tmp.x * tmp.x);
			Q.push(Loc(tmp.x * tmp.x, tmp.str + "*"));
		}
		if (0 <= tmp.x + tmp.x&&tmp.x + tmp.x <= maxi && ch.count(tmp.x + tmp.x) == 0) {
			ch.insert(tmp.x + tmp.x);
			Q.push(Loc(tmp.x + tmp.x, tmp.str + "+"));
		}
		if (0<=tmp.x-tmp.x&&tmp.x - tmp.x < maxi && ch.count(tmp.x - tmp.x) == 0) {
			ch.insert(tmp.x - tmp.x);
			Q.push(Loc(tmp.x - tmp.x, tmp.str + "-"));
		}
		if (tmp.x != 0 && tmp.x / tmp.x < maxi && ch.count(tmp.x / tmp.x) == 0) {
			ch.insert(tmp.x / tmp.x);
			Q.push(Loc(tmp.x / tmp.x, tmp.str + "/"));
		}
	}

	cout << -1 << '\n';
	return 0;
}