(c++)백준 14395번: 4연산

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

14395번: 4연산

[풀이]

bfs를 사용했다.

연산의 아스키 코드 순서대로 queue에 푸시해주었기 때문에 값이 t가 되면 바로 그때까지 했던 연산들을 출력하면 된다.

set자료구조에 나온 값을 저장하여 같은 값에 대해 더 이상 탐색하지 않게 했다.

/연산으로 인해 나오는 1은  처음 한 번만 나오면 되므로 set을 탐색하지 않고 boolean값으로 사용 여부를 체크했다.

사실 -는 쓸일이 없다. (t는 항상 1보다 큰데 -를 쓰면 0이 되기 때문에)

 

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

struct Cal {
	long long num;//연산된 값
	string cal;//연산 횟수
};

int s, t;
set<long long>Num;

void bfs() {
	queue<Cal>q;
	q.push({ s,"" });
	int ans = -1;
	Num.insert(s);
	bool divided = false;
	while (!q.empty()) {
		long long num = q.front().num;
		string cal = q.front().cal;
		int cal_len = cal.length();
		q.pop();
		if (num == t) {
			cout << cal << '\n';
			return;
		}

		//*
		long long nnum = num * num;
		if (nnum <= t && Num.find(nnum) == Num.end()) {
			q.push({ nnum,cal + '*' });
			Num.insert(nnum);
		}

		//+
		nnum = num + num;
		if (nnum <= t && Num.find(nnum) == Num.end()) {
			q.push({ nnum,cal + '+' });
			Num.insert(nnum);
		}

		//-
		nnum = num - num;
		if (Num.find(nnum) == Num.end()) {
			q.push({ nnum,cal + '-' });
			Num.insert(nnum);
		}

		//'/
		if (!divided && num != 0) {
			nnum = num / num;
			q.push({ nnum,cal + '/' });
			Num.insert(nnum);
			divided = true;
		}
	}
	cout << -1 << '\n';
}

void solution() {
	cin >> s >> t;
	if (s == t)
		cout << 0 << '\n';
	else {
		bfs();
	}
}

int main() {
	solution();
	return 0;
}