백준(BOJ) 4연산

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

14395번: 4연산

풀이 :

 

t가 10억이지만 n은 2*n 의 형태나 n^2 의 형태이기 때문에 탐색하는 n의 수는 많지 않고 BFS로 접근할 수 있다.

 

queue<pair<long long, string>> q를 생성한후에 * + - / 각각의 순서대로 결과값과 그때의 붙는 부등호의 값을

 

큐에 넣는다. 

 

조건은 10억이하일 경우 q에 넣어야 하고 나눌때에 n은 0이여서는 안된다. 또 같은 값을 다시 넣지 않기 위해

 

stl set을 통하여 중복을 막아주자.

 

코드 ( C++ )

 

	#include <iostream>
	#include <queue>
	#include <string>
	#include <set>
	using namespace std;
	int s, t;
	const long long MAX = 1000000000LL;
	int main()
	{
	cin >> s >> t;
	if (s == t) {
	cout << 0 << "\n";
	return 0;
	}
	queue<pair<long long, string>> q;
	set<long long> visited;
	q.push({ s, ""});
	while (!q.empty())
	{
	long long n = q.front().first;
	string temp = q.front().second;
	if (n == t) {
	cout << temp << "\n";
	return 0;
	}
	q.pop();
	if (0 <= n*n && n*n <= MAX && visited.count(n*n) == 0 ) {
	q.push({ n*n, temp + "*" });
	visited.insert(n*n);
	}
	if (0 <= n + n && n + n <= MAX && visited.count(n+n) == 0) {
	q.push({ n + n, temp + "+" });
	visited.insert(n + n);
	}
	if (0 <= n - n && n - n <= MAX && visited.count(n-n) == 0) {
	q.push({ n - n, temp + "-" });
	visited.insert(n - n);
	}
	if (n != 0 && 0 <= n / n && n / n <= MAX && visited.count(n/n) == 0) {
	q.push({ n / n, temp + "/" });
	visited.insert(n / n);
	}
	}
	cout << -1 << "\n";
	return 0;
	}

view raw .cpp hosted with ❤ by GitHub