BOJ 14395 : 4연산

풀이

---

문제 풀어보기

 

유사문제

2020/03/06 - [백준 문제풀이/GRAPH] - BOJ 12906 : 새로운 하노이 탑

BOJ 12906 : 새로운 하노이 탑

 

코드

---

#include <iostream>
#include <algorithm>
#include <queue>
#include <array>
#include <map>

using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	long long st, end;
	cin >> st >> end;

	string s = "";
	map< long long, string> d;
	queue<pair<string, long long> > q;
	q.push({ s, st });
	d[st] = s;


	while (!q.empty()) {
		string now_s = q.front().first;
		long long now_i = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++) {
			auto next_s = now_s;
			auto next_i = now_i;
			if (i == 1) {
				next_s += '+';
				next_i += now_i;
			}
			else if (i == 2) {
				next_s += '-';
				next_i -= now_i;
			}
			else if (i == 0) {
				next_s += '*';
				next_i *= now_i;
			}
			else if(i==3 && now_i != 0 ) {
				next_s += '/';
				next_i /= now_i;
			}
			if (d.count(next_i) == 0) {
				q.push({ next_s, next_i });
				d[next_i] = next_s;
			}

		}
	}

	if (st == end) {
		cout << 0 << '\n';
	}
	else if (d.count(end) == 0) {
		cout << -1 << '\n';
	}
	else {
		cout << d[end] << '\n';
	}
	return 0;
}