글 읽기 - KAIST [A Plus Equals B] 문제 접근법이 궁금합니다.

park780172 4년 전 0

문제를 읽고 bfs나 백트래킹, 브루트 포스 같은 문제로 생각하였습니다.

일단은 bfs로 구현하면서 시간 초과 날 것 같았는데 역시나 나더라구요..

하여튼

모든 경우를 탐색하여 A와 B가 같은 경우를 찾는 방법 밖에 없는 것 같은데

혹시 조그마한 힌트나 다른 알고리즘을 써야하는지 말씀해주실 수 있으실까요...?ㅠ

정답자 분들의 정답 코드 길이는 매우 짧더라구요.

제 시간 초과 코드는 그냥 제물로 드리겠습니다..

#include <bits/stdc++.h>

using namespace std;

long long A, B;

map<pair<long long, long long>, int> m;

queue< pair<vector<string>, pair<long long, long long>> > q;

vector<string> bfs()
{
	vector<string> vc;

	q.push({ vc, {A, B} });

	while (!q.empty())
	{
		int qSize = q.size();

		while (qSize--)
		{
			long long a = q.front().second.first;
			long long b = q.front().second.second;
			vector<string> vs = q.front().first;

			q.pop();

			if (a == b) return vs;

			if (!m.count({ 2 * a, b }))
			{			
				vs.push_back("A+=A");
				m[{ 2 * a, b }] = 1;
				q.push({ vs,{ 2 * a, b } });
				vs.pop_back();
			}

			if (!m.count({ a + b, b }))
			{
				vs.push_back("A+=B");
				m[{ a + b, b }] = 1;
				q.push({ vs,{ a + b, b } });
				vs.pop_back();
			}

			if (!m.count({ a, b + a }))
			{
				vs.push_back("B+=A");
				m[{ a, b + a }] = 1;
				q.push({ vs,{ a, b + a } });
				vs.pop_back();
			}

			if (!m.count({ a, 2 * b }))
			{
				vs.push_back("B+=B");
				m[{ a, 2 * b }] = 1;
				q.push({ vs,{ a, 2 * b } });
				vs.pop_back();
			}
		}	
	}

	vector<string> emt;

	return emt;
}

int main(void)
{
	scanf("%lld %lld", &A, &B);

	vector<string> ans = bfs();

	printf("%d\n", ans.size());

	for (auto i : ans)
		cout << i << '\n';
	
	return 0;
}