[BFS] 4연산

예제 입력 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

/

 

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

14395번: 4연산

 

- 문제의 조건에서 s와 t의 최대값이 10의 9승이므로 (=10억) 배열을 이용할 수 없다. 체크하기 위해서 set를 사용.

- 숫자의 최대값에 비해 실제 연산횟수는 그렇게 많지 않다. -는 0으로 만들어버리게 되고 /는 1로 만드는 연산이므로 크게 중요하지 않고, +는 2x로 *는 x^2의 형태로 변형만 가능하기 때문이다. 즉, 변형 가능한 형태는 x^a * 2^b의 형태이다. 

- 사전순으로 *, +, -, /로 출력해라고 했으므로 이 순서대로 조건을 검사한다.

 

#include <stdio.h>
#include <set>
using namespace std;

const int MAX_SIZE = 1000;
const int MAX_QUEUE_SIZE = 1000;
const long long limit = 1000000000LL;

set<long long> checked;
long long S, T;

class vector
{
public:
	int size;
	char items[MAX_SIZE];

	vector() { size = 0; }

	void add(char item)
	{
		items[size] = item;
		size++;
	}
};

class operPair
{
public:
	long long number;
	vector v;

	operPair() {}
	operPair(long long number) : number(number) {}
	operPair(long long number, vector v) : number(number), v(v) {}
};

template <typename T>
class Queue
{
private:
	int front;
	int rear;
	T items[MAX_QUEUE_SIZE];

public:
	Queue() { front = rear = 0; }
	
	void push(T item)
	{
		items[rear] = item;
		rear = (rear + 1) % MAX_QUEUE_SIZE;
	}

	T pop()
	{
		T result = items[front];
		front = (front + 1) % MAX_QUEUE_SIZE;

		return result;
	}

	bool isEmpty()
	{
		return front == rear;
	}
};
Queue<operPair> q;

int main(void)
{
	scanf("%lld %lld", &S, &T);

	if (S == T)
	{
		printf("0\n");
		return 0;
	}

	checked.insert(S);
	operPair init(S);
	q.push(init);

	while (!q.isEmpty())
	{
		operPair now = q.pop();

		if (now.number == T)
		{
			int size = now.v.size;

			for (int i = 0; i < size; i++)
			{
				printf("%c", now.v.items[i]);
			}
			printf("\n");
			return 0;
		}

		//*
		if (0 <= (now.number * now.number) && (now.number * now.number) <= limit && checked.count(now.number * now.number) == 0)
		{
			operPair next(now.number * now.number, now.v);
			next.v.add('*');

			checked.insert(next.number);
			q.push(next);
		}
		// +
		if (0 <= (2 * now.number) && (2 * now.number) <= limit && checked.count(2 * now.number) == 0)
		{
			operPair next(2 * now.number, now.v);
			next.v.add('+');

			checked.insert(next.number);
			q.push(next);
		}
		// -
		if (0 <= (now.number- now.number) && (now.number - now.number) <= limit && checked.count(now.number - now.number) == 0)
		{
			operPair next(now.number - now.number, now.v);
			next.v.add('-');

			checked.insert(next.number);
			q.push(next);
		}
		// /
		if (now.number != 0 && 0 <= (now.number / now.number) && (now.number / now.number) <= limit && checked.count(now.number / now.number) == 0)
		{
			operPair next(now.number / now.number, now.v);
			next.v.add('/');

			checked.insert(next.number);
			q.push(next);
		}
	}

	printf("-1\n");
	return 0;
}