백준 12886 c++ 돌 그룹

https://www.acmicpc.net/problem/12886

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을 출력한다.

---

틀린코드(메모리 초과)

#include <iostream>
#include <queue>
using namespace std;

int a, b, c;
int result = 0;
bool visit[1501][1501][1501];

struct group
{
	int A;
	int B;
	int C;
};//먼저 그룹 3개를 만듬

void pick(int& small, int& big)
{
	if (small == big)
		return;
	if (small > big)
	{
		int tmp = big;
		big = small;
		small = tmp;
	}
	big = big - small;
	small = small * 2;

}

void bfs()
{
	queue<group> q;
	q.push({ a,b,c });
	visit[a][b][c] = true;
	while (!q.empty())
	{
		int nowA = q.front().A;
		int nowB = q.front().B;
		int nowC = q.front().C;//3가지 현재 그룹 지정
		q.pop();
		if ((nowA == nowB) && (nowA == nowC))// 3개 같으면 리턴
		{
			result = 1;
			return;
		}
		for (int i = 0; i < 3; i++)
		{
			int nextA = nowA;
			int nextB = nowB;
			int nextC = nowC;
			if (i == 0)
			{
				pick(nextA, nextB);
				if (visit[nextA][nextB][nextC])
					continue;
				cout << nextA << nextB << nextC << '\n';
				visit[nextA][nextB][nextC] = true;
				q.push({ nextA, nextB, nextC });
			}
			if (i == 1)
			{
				pick(nextA, nextC);
				if (visit[nextA][nextB][nextC])
					continue;
				cout << nextA << nextB << nextC << '\n';
				visit[nextA][nextB][nextC] = true;
				q.push({ nextA, nextB, nextC });
			}
			if (i == 2)
			{
				pick(nextB, nextC);
				if (visit[nextA][nextB][nextC])
					continue;
				cout << nextA << nextB << nextC << '\n';
				visit[nextA][nextB][nextC] = true;
				q.push({ nextA, nextB, nextC });
			}
		}
	}
	return;
}

int main()
{
	cin >> a >> b >> c;
	bfs();
	cout << result;
}

 

---

맞은 코드

#include <iostream>
#include <queue>
using namespace std;

int a, b, c;
int result = 0;
bool visit[1501][1501];
int sum;

struct group
{
	int A;
	int B;
};//2개만 만들어도 됨

void pick(int& small, int& big)
{
	if (small == big)
		return;
	if (small > big)
	{
		int tmp = big;
		big = small;
		small = tmp;
	}
	big = big - small;
	small = small * 2;

}

void bfs()
{
	queue<group> q;
	q.push({ a,b });
	visit[a][b] = true;
	while (!q.empty())
	{
		int nowA = q.front().A;
		int nowB = q.front().B;//3가지 현재 그룹 지정 // C는 자동 배정 sum - a - b
		q.pop();
		if ((nowA == nowB) && (nowA == sum-nowA-nowB))// 3개 같으면 리턴
		{
			result = 1;
			return;
		}
		for (int i = 0; i < 3; i++)
		{
			int nextA = nowA;
			int nextB = nowB;
			int nextC = sum - nowA - nowB;
			if (i == 0)
			{
				pick(nextA, nextB);
				if (visit[nextA][nextB])
					continue;
				visit[nextA][nextB] = true;
				q.push({ nextA, nextB });
			}
			if (i == 1)
			{
				pick(nextA, nextC);
				if (visit[nextA][nextC])
					continue;
				visit[nextA][nextC] = true;
				q.push({ nextA, nextC });
			}
			if (i == 2)
			{
				pick(nextB, nextC);
				if (visit[nextB][nextC])
					continue;
				visit[nextB][nextC] = true;
				q.push({ nextB, nextC });
			}
		}
	}
	return;
}

int main()
{
	cin >> a >> b >> c;
	sum = a + b + c;
	bfs();
	cout << result;
}

틀린코드에서는 struct를 활용하여 큐에 변수 3개를 넣었고, A,B,C각각 체크?방문을 기록하는 bool형 배열 역시 3차원으로 체크하였다보니 메모리초과가 나서 틀렸다.

 

맞은 코드드에서는 3개의 그룹 중 2개의 값이 정해지면 나머지 하나는 자동적으로 sum - a - b로 정해진다는 것을 이용하여 struct의 변수 개수를 줄이고 visit 배열 역시 2차원으로 줄여 메모리를 줄였다.