[백준/C++] 14395 4연산

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

코드

#include <iostream>
#include <queue>
#include <set>
using namespace std;

#define MAX 1000000001
#define FASTIO ios::sync_with_stdio(false); cin.tie(NULL);
typedef long long ll;
typedef pair<ll, string> p;
set<ll> visit;

int s, t;
void bfs() {
	queue<p> q;

	q.push({ s, "" });
	visit.insert(s);

	if (s == t) {
		cout << 0;
		return;
	}

	while (!q.empty()) {
		ll now = q.front().first;
		string st = q.front().second;
		q.pop();

		if (now == t) {
			cout << st;
			return;
		}

		if (now * now < MAX && visit.find(now * now) == visit.end()) {
			visit.insert(now * now);
			q.push({ now * now, st + "*" });
		}

		if (now + now < MAX && visit.find(now + now) == visit.end()) {
			visit.insert(now + now);
			q.push({ now + now, st + "+" });
		}

		if (visit.find(now - now) == visit.end()) {
			visit.insert(now - now);
			q.push({ now - now, st + "-" });
		}

		if (now != 0 && visit.find(now / now) == visit.end()) {
			visit.insert(now / now);
			q.push({ now / now, st + "/" });
		}
	}
	cout << -1;
	return;
}

int main() {
	FASTIO;
	cin >> s >> t;
	bfs();
	return 0;
}

 

설명

*, +, - , / 순으로 bfs를 돌리면서 now가 t가 되는지 확인하면 된다. 

느낀 점

아이디어 자체는 바로 생각했는데, 구현하면서 메모리 초과와 틀렸습니다를 만났다. 처음에 bool 배열로 방문 관리를 했는데 메모리 초과가 발생했다. 그래서 set으로 변경해서 코드를 작성했다. 이 코드는 틀렸는데 코드를 살펴보니 방문 확인 순서에서 틀린 부분이 있어서였다. 반례 게시판의 반례 덕분에 이 문제를 찾았다..

 

고쳐서 제출하니 맞았다!