[백준] 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을 출력한다.

---

풀이)

중복된 돌의 개수를 어떻게 처리해야 할지 고민이 많았던 문제이다.

처음엔 A,B,C 3개의 돌 개수를 모두 중복 처리하기위해 set을 이용했었다.

#typedef tuple <int,int,int> T;

set <pair<int<pair<int,int>>;  or  set <T>;이런식으로

그런데 3개의 수로 중복처리를 하니 너무 많은 케이스들이 존재해 시간이 오래걸렸다.

다른분의 풀이를 보고 생각을 다르게 해도 됨을 깨달았다.

어차피 A, B, C 돌의 개수의 합 SUM은 변하지 않으므로, 돌의 개수는 두 개만 계속 확인하면 된다.

나머지 하나는 자동적으로 SUM - (나머지 두 개 돌의 합)

이렇게 하니 두개의 숫자만 가지고 중복처리를 할 수 있게 되었다.

int visit[i][j] // 돌 하나의 개수가 i, 또다른 돌의 개수가 j일때가 존재할 수 있는지 여부

   (자연스럽게 나머지 돌 하나는 SUM - i - j개)

정답은 visit[SUM/3][SUM /3] 만 확인해보면된다.

코드)

#include <stdio.h>
#include <queue>
using namespace std;
int A, B, C, SUM;
bool visit[1501][1501];
 
int main() {
    scanf("%d %d %d", &A, &B, &C);
    SUM = A + B + C;
 
    if (SUM % 3 != 0) {//A,B,C 똑같이 공평하게 분배 불가능 하면 바로 0 return
        printf("0\n");
        return 0;
    }
 
    queue<pair<int,int>> qu;
    qu.push({ A,B });
    visit[A][B] = true;
    int a, b;
 
    while (!qu.empty())
    {
        a = qu.front().first;
        b = qu.front().second;
        //3개 돌의 개수저장하는 temp
        int temp[3] = { a, b, SUM - a - b }; // c = sum - a - b
        qu.pop();
        
        for (int i = 0; i < 3; i++) {//3개의 수로 가능한 조합 
            for (int j = 0; j < 3; j++) {
                
                if (temp[i] < temp[j]) {
                    int num1 = temp[i] * 2;
                    int num2 = temp[j] - temp[i];
                    if (visit[num1][num2]) continue;
 
                    visit[num1][num2] = true;
                    qu.push({ num1,num2 });
                }
            }
        }
    }
    printf("%d\n", visit[SUM / 3][SUM / 3]);
    return 0;
}