백준 12886번 돌 그룹

문제

오늘 강호는 돌을 이용해 재미있는 게임을 하려고 한다. 먼저, 돌 세개는 그룹으로 나누어져 있으며 각각의 그룹에는 돌이 A, B, C개가 있다. 강호는 모든 그룹에 있는 돌의 개수를 같게 만들려고 한다.

강호는 돌을 단계별로 움직이며, 각 단계는 다음과 같이 이루어져 있다.

크기가 같지 않은 두 그룹을 고른다. 그 다음, 돌의 개수가 작은 쪽을 X, 큰 쪽을 Y라고 정한다. 그 다음, X에 있는 돌의 개수를 X+X개로, Y에 있는 돌의 개수를 Y-X개로 만든다.

A, B, C가 주어졌을 때, 강호가 돌을 같은 개수로 만들 수 있으면 1을, 아니면 0을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 A, B, C가 주어진다. (1 ≤ A, B, C ≤ 500)

출력

돌을 같은 개수로 만들 수 있으면 1을, 아니면 0을 출력한다.

 

 

간단한 문제인데 , visit 처리가 조금 애매

배열로 처리하면 메모리 초과이므로 string으로 하려 했으나 string 생성 과정에서 시간초과가 발생.

따라서 struct 형태로 표현했지만 왠지 컴파일 문제가 발생해서

마지막으로 그냥 pair키로 직접 때려넣었더니 해결 !

#include<iostream>
#include <string.h>
#include<string>
#include<queue>
#include <vector>
#include<map>

using namespace std;



struct Node
{
	int a;
	int b;
	int c;
};
map < pair<pair<int,int> ,int>, bool> m;


int main(void)
{
	int A, B, C;
	cin >> A >> B >> C;
	m[{ {A, B}, C}] = true;

	queue<Node> que;
	que.push({ A,B,C });

	while (!que.empty())
	{
		int a = que.front().a;
		int b = que.front().b;
		int c = que.front().c;

		que.pop();
		if (a == b && b == c)
		{
			cout << 1 << endl;
			return 0;
		}

		if (a < b)
		{
			if (!m[{ {a + a, b - a}, c}])
			{
				m[{ {a + a, b - a}, c}] = true;
				que.push({ a + a,b - a,c });
			}
		}

		if (a < c)
		{
			if (!m[{ {a + a, b}, c - a}])
			{
				m[{ {a + a, b}, c - a}] = true;
				que.push({ a + a,b,c -a });
			}
		}

		if (b < a)
		{
			if (!m[{ {a - b, b + b}, c}])
			{
				m[{ {a - b, b + b}, c}] = true;
				que.push({ a - b,b + b,c});
			}
		}

		if (b < c)
		{
			if (!m[{ {a, b + b}, c - b}])
			{
				m[{ {a, b + b}, c - b}] = true;
				que.push({ a ,b + b,c - b});
			}
		}

		if (c < b)
		{
			if (!m[{ {a, b - c}, c + c}])
			{
				m[{ {a, b - c}, c + c}] = true;
				que.push({ a ,b - c,c + c });
			}
		}

		if (c < a)
		{
			if (!m[{ {a - c, b}, c + c}])
			{
				m[{ {a - c, b}, c + c}] = true;
				que.push({ a - c ,b ,c + c });
			}
		}
	}

	cout << 0 << endl;
}