4연산

문제

정수 s가 주어진다. 정수 s의 값을 t로 바꾸는 최소 연산 횟수를 구하는 프로그램을 작성하시오.

사용할 수 있는 연산은 아래와 같다.

1. s = s + s; (출력: +)
2. s = s - s; (출력: -)
3. s = s * s; (출력: *)
4. s = s / s; (출력: /) (s가 0이 아닐때만 사용 가능)

입력

첫째 줄에 s와 t가 주어진다. (1 ≤ s, t ≤ 109)

출력

첫째 줄에 정수 s를 t로 바꾸는 방법을 출력한다. s와 t가 같은 경우에는 0을, 바꿀 수 없는 경우에는 -1을 출력한다. 가능한 방법이 여러 가지라면, 사전 순으로 앞서는 것을 출력한다. 

연산의 아스키 코드 순서는 '*', '+', '-', '/' 이다.

#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <string>

using namespace std;

//1시간 54분 
// 너무 쓸데없는데에 시간 허비함 -> 처음 s push 할때 check 기록안해줘서 계속 틀림, type longlong 안해줘서 틀리기도함

int main() {
	
	ios_base::sync_with_stdio(0); 
	cin.tie(0);

	queue<long long>q;
	map<long long, string>check;

	long long s;
	long long t;

	cin >> s;
	cin >> t;

	if (s == t) { cout << "0" << '\n'; return 0; }

	q.push(s);
	bool ans = false;  
	check[s] = "s";  // 이런거 실수 하지말자 바보야...

	while (!q.empty()) {

		long long num = q.front();
		q.pop();

		if (num == t) { ans = true;  break; }
		

		long long c =0;

		c = num*num; 
	
		if (check[c].empty()) {
			check[c] = check[num];
			if (check[c] == "s") { check[c].clear(); }  //연산 처음 시작 부분일때 "s" 포함되는데 이거 제거하기
			check[c] += "*";
			q.push(c);
		}

		c = num + num;

		if (check[c].empty()) {
			check[c] = check[num];
			if (check[c] == "s") { check[c].clear(); }  //연산 처음 시작 부분일때 "s" 포함되는데 이거 제거하기
			check[c] += "+";
			q.push(c);

		}

		c = num - num;

		if (check[c].empty()) {
			check[c] = check[num];
			if (check[c] == "s") { check[c].clear(); }  //연산 처음 시작 부분일때 "s" 포함되는데 이거 제거하기
			check[c] += "-";
			q.push(c);
		}

		if (num != 0) {
			c = num / num;
			if (check[c].empty()) {
				check[c] = check[num];
				if (check[c] == "s") { check[c].clear(); }  //연산 처음 시작 부분일때 "s" 포함되는데 이거 제거하기
				check[c] += "/";
				q.push(c);
			}
		}

	}

	if (ans == false) { cout << "-1" << endl; return 0; }
	
	cout << check[t];

	cout << '\n';
	return 0;

}