백준 14395번 4연산

문제 링크입니다: https://www.acmicpc.net/problem/14395

14395번: 4연산

사칙연산의 우선순위가 있기 때문에 *, +, / 순으로 큐에 Node를 push 하도록 코드를 작성했습니다.

- 같은 경우 s, t 모두 0이 될 수 없으므로 로직에 포함시키지 않았습니다.

중복된 s를 계산하지 않기 위해 map을 사용했고 각 과정을 Node 구조체의 process 문자열에 저장했습니다.

마지막으로 / 같은 경우 1은 한번만 등장하면 되기 때문에 별도의 boolean 변수 flag를 이용하여 한번만 계산하도록 했습니다.

 

	#include <iostream>
	#include <string>
	#include <queue>
	#include <map>
	using namespace std;
	typedef struct
	{
	long long s;
	string process;
	} Node;
	map<long long, bool> visited;
	int main(void)
	{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	long long s, t;
	cin >> s >> t;
	if (s == t)
	{
	cout << 0 << "\n";
	return 0;
	}
	queue<Node> q;
	q.push({ s, "" });
	bool flag = true;
	while (!q.empty())
	{
	int qSize = q.size();
	for (int i = 0; i < qSize; i++)
	{
	Node node = q.front();
	q.pop();
	if (node.s == t)
	{
	cout << node.process << "\n";
	return 0;
	}
	long long temp = node.s * node.s;
	if (temp <= t && visited.count(temp) == false)
	{
	q.push({ temp, node.process + '*' });
	visited[temp] = true;
	}
	temp = node.s * 2;
	if (temp <= t && visited.count(temp) == false)
	{
	q.push({ temp, node.process + '+' });
	}
	if (flag)
	{
	q.push({ 1, node.process + '/' });
	flag = false;
	}
	}
	}
	cout << -1 << "\n";
	return 0;
	}

view raw .cpp hosted with ❤ by GitHub

개발환경:Visual Studio 2017

 

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~