boj,백준) 12886. 돌그룹(C/C++)

1. 문제 링크

www.acmicpc.net/problem/12886

12886번: 돌 그룹

2. 문제 개요

A, B, C 3개의 돌이 있다. 모든 그룹에 있는 돌의 개수를 같게 만들려고 한다.

크기가 같지 않은 두 그룹을 고른다. 그다음, 돌의 개수가 작은 쪽을 X, 큰 쪽을 Y라고 했을 때, X는 X+X로, Y는 Y-X개로 만든다. A, B, C가 주어졌을 때, 강호가 돌을 같은 개수로 만들 수 있으면 1을, 아니면 0을 출력하는 프로그램을 작성하시오.

 

3. 문제 힌트

가장 간단하게 생각해보면 모든 경우의수를 조사하는 것. 그런데, 세 돌의 순서도 상관없고, 전수조사할 때 조사했던 것을 또 조사하지 않고 넘어갈 수 있는 방법은 없을까??

 

각 돌의 무게가 500이니까 500x500x500 배열을 사용해서 이미 조사했음을 나타내어도 괜찮을까?

-> 각 돌의 무게는 500을 초과할 수 있고, 500x500x500만해도 충분히 크다.

 

수학적으로 문제를 풀 수 있는걸까? 공간을 줄일 수 있을까? 생각해보자.

 

4. 문제 풀이

처음에 바로 생각난 것은 전수조사를 하되, DP처럼 조사했던 것에 대한 기록을 남겨놓아서 무한반복이 일어나지 않게 하자 라는 것이다. 이렇게 하면 시간복잡도도 줄어든다.

 

공간을 생각해보았는데,

이것도 가장 먼저 떠오른게 500x500x500 배열을 만들어 기록하는 것이었다.  ->무리

그래서 공간을 줄이거나, 내가 생각하지 못한 수학적으로 바로 풀 수 있는 방법이 있는지 생각해보았다.

뭔가 반복이 일어나지 않게 하기 위해서 '방문'했다는 것만 구별할 수 있게 한다면 BFS로도 충분히 풀 수 있겠다 싶었다.

 

계속 생각해봤는데 몇 규칙을 찾을 수 있었다.

우선, a+b+c는 항상 일정하다는 것이다. 규칙에 따르면, X, Y, Z가 있다고 할 때(오름차순), 값은 X+X, Y, Z-X로 합은 X+Y+Z로 전과 동일해진다.

★따라서, 공간을 3차원으로 설정하지 않고 2차원으로 설정해도 나머지 1차원의 값이 자동으로 결정되는 것을 알 수 있었다.

결론은 2차원 배열만 가지고 방문 처리를 해도 값에 문제가 없다, 라는 것이다.

그래서 도중에 나올 수 있는 최대값 1500까지 포함하는 2차원 배열을 선언하고 BFS로 탐색을 진행해서 문제를 풀었다.

 

5. 코드

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

int a, b, c;

struct COORD {
	COORD(){}
	COORD(int x_, int y_, int z_) :x(x_), y(y_), z(z_) {}
	int x, y, z;
};

queue<COORD> q;
bool visited[1501][1501];

int main()
{
	cin >> a >> b >> c;

	if ((a + b + c) % 3 != 0)
	{
		cout << '0';
		return 0;
	}

	q.push(COORD(a, b, c));

	while (!q.empty()){
		COORD cur = q.front(); q.pop();
		
		if (cur.x == cur.y && cur.y == cur.z)
		{
			cout << '1';
			return 0;
		}

		int sorted[3];
		sorted[0] = cur.x;
		sorted[1] = cur.y;
		sorted[2] = cur.z;
		sort(sorted, sorted + 3);

		//1,2
		int next[3];
		if (sorted[0] != sorted[1]) {
			next[0] = sorted[0] * 2;
			next[1] = sorted[1] - sorted[0];
			next[2] = sorted[2];
			if (!visited[next[0]][next[1]]) {
				visited[next[0]][next[1]] = true;
				q.push(COORD(next[0], next[1], next[2]));
			}
		}
		//1,3
		if (sorted[0] != sorted[2]) {
			next[0] = sorted[0] * 2;
			next[1] = sorted[1];
			next[2] = sorted[2] - sorted[0];
			if (!visited[next[0]][next[1]]) {
				visited[next[0]][next[1]] = true;
				q.push(COORD(next[0], next[1], next[2]));
			}
		}
		//2,3
		if (sorted[1] != sorted[2]) {
			next[0] = sorted[0];
			next[1] = sorted[1] * 2;
			next[2] = sorted[2] - sorted[1];
			if (!visited[next[0]][next[1]]) {
				visited[next[0]][next[1]] = true;
				q.push(COORD(next[0], next[1], next[2]));
			}
		}
	}

	cout << '0';
	return 0;
}

 

6. 결과