[BOJ/Gold 5] 백준 14395 4연산(C++)

문제 링크

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

14395번: 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을 출력한다. 가능한 방법이 여러 가지라면, 사전 순으로 앞서는 것을 출력한다. 

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

예제 입력 1

7 392

예제 출력 1

+*+

예제 입력 2

7 256

예제 출력 2

/+***

예제 입력 3

4 256

예제 출력 3

**

예제 입력 4

7 7

예제 출력 4

0

예제 입력 5

7 9

예제 출력 5

-1

예제 입력 6

10 1

예제 출력 6

/

알고리즘 분류

• 자료 구조
• 그래프 탐색

풀이

계산 중에 정수의 범위를 넘어설 수 있으므로 long long형으로 자료형을 바꿔 주고, set 자료구조를 이용하여 결과값을 방문했는지 방문하지 않았는지를 파악하였다.

코드

#include <iostream>
#include <string>
#include <cmath>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#define FIRST cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX 1000000000
#define LL long long
#define INF 2e9

using namespace std;
LL S, T;
char OP[4] = { '*','+','-','/' };
set<LL> SET;

string BFS(LL X) {
	queue<pair<LL, string> > Q;
	Q.push(make_pair(X, ""));

	while (!Q.empty()) {
		LL CurX = Q.front().first;
		string CurStr = Q.front().second;
		Q.pop();

		if (CurX == T) {
			return CurStr;
		}

		LL nextX;
		// 곱하기
		nextX = CurX * CurX;
		if (SET.find(nextX) == SET.end()) {
			SET.insert(nextX);
			Q.push(make_pair(nextX, CurStr + "*"));
		}

		// 더하기
		nextX = CurX + CurX;
		if (SET.find(nextX) == SET.end()) {
			SET.insert(nextX);
			Q.push(make_pair(nextX, CurStr + "+"));
		}

		// 빼기
		nextX = 0;
		if (SET.find(nextX) == SET.end()) {
			SET.insert(nextX);
			Q.push(make_pair(nextX, CurStr + "-"));
		}

		// 나누기
		if (CurX != 0) {
			nextX = 1;
			if (SET.find(nextX) == SET.end()) {
				SET.insert(nextX);
				Q.push(make_pair(nextX, CurStr + "/"));
			}
		}
	};

	return "-1";
}

int main() {
	FIRST
	cin >> S >> T;
	if (S == T) {
		cout << 0 << "\n";
	}
	else {
		cout << BFS(S) << "\n";
	}

	return 0;
}