[백준] 14395번 - 4연산 / C++

문제

정수 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 <string>
#include <queue>
#include <set>

using namespace std;

long long S;
long long T;
string answer = "";

long long calc(long long n, char op)
{
	if (op == '*')		return n * n;
	if (op == '+')		return n + n;
	if (op == '-')		return n - n;
	if (op && op == '/')	return n / n;
}

void bfs()
{
	queue< pair<long long, string> > q;
	pair<long long, string> curr;
	set<long long> check;
	char op[] = {'*', '+', '-', '/'};
	long long res;
	int i;

	check.insert(S);
	q.push(make_pair(S, ""));
	while (!q.empty())
	{
		curr = q.front();
		q.pop();
		// 현재까지 구한 방법의 길이보다 길다면 더 이상 사전 순으로 앞서는 방법을 찾을 수 없으므로 리턴
		if (!answer.empty() && (curr.second.size() > answer.size()))
		{
			return;
		}
		// S를 T로 바꾸었다면 가장 앞서는 방법으로 갱신
		if (curr.first == T)
		{
			if (answer.empty())
				answer = curr.second;
			else if (curr.second < answer)
				answer = curr.second;
		}
		// 4개의 연산자에 대해 아스키 코드 순서대로 확인
		for (i = 0; i < 4; i++)
		{
			// 연산 결과를 구함
			res = calc(curr.first, op[i]);
			// 확인된 적이 없는 값이면 추가
			if (check.find(res) == check.end())
			{
				check.insert(res);
				q.push(make_pair(res, curr.second + op[i]));
			}
		}
	}
}

int main()
{
	cin >> S >> T;
	if (S == T)
	{
		cout << 0 << endl;
	}
	else
	{
		bfs();
		if (answer.empty())
			cout << -1 << endl;
		else
			cout << answer << endl;		
	}
	return 0;
}

 

링크

14395번: 4연산

inbdni/Baekjoon