백준 12886번: 돌 그룹

문제링크 :https://www.acmicpc.net/problem/12886

12886번: 돌 그룹

 

 문제설명 

 

1. 돌그룹 세개가 주어졌을떄 크기가 같지 않은 두 그룹을 고른다.

2. 돌의 개수가 작은 쪽을 X, 큰 쪽을 Y라고 정한다.

3.그 다음, X에 있는 돌의 개수를 X+X개로, Y에 있는 돌의 개수를 Y-X개로 만든다.

4.위 과정을 거쳐서 돌을 균등하게 나눌 수있는지 확인

 

 알고리즘 

 

1. 돌의 갯수를 다더해 3으로 나누어 지는지 확인한다 -> 나눠지지 않으면 0 출력

2. 나눠진다면 (A>B) (B>A) (A>C) (C>A) (B>C) (C>B) 6가지 그룹을 비교하고 연산을 진행한다

3. 비교 연산을 진행하면서 이떄 까지 나왔던 수 조합이면 큐에 넣지않고 처음 나오는 조합이면 큐에 넣는다.

4. 위 과정을 Q가 empty 될떄까지 반복후 균등하게 나눠진다면 1을 출력 아니면 0을출력.

 

 코드 

#include<iostream>
#include<algorithm>
#include<queue>
#include<set>
 
 
using namespace std;
 
int A, B, C;
 
set < pair<pair<int, int>, int>> check;
queue<pair<pair<int, int>, int>> q;
 
 
int main() {
    cin.tie(NULL);
    ios::sync_with_stdio(false);
 
    cin >> A >> B >> C;
    q.push(make_pair(make_pair(A, B), C));
 
    //돌을 같은 갯수로 나눌 수 없다.
    if ((A + B + C) % 3 != 0) {
        cout << 0;
        return 0;
    }
 
    bool pos = false;
    while (!q.empty()) {
        int a = q.front().first.first;
        int b = q.front().first.second;
        int c = q.front().second;
 
        q.pop();
 
        if (a == b && b == c && c == a) {
 
            pos = true;
            break;
        }
 
        int aa, bb, cc;
 
        if (a > b) {
            aa = a - b;
            bb = b + b;
            cc = c;
            //같은 수 조합이 나온적 있는지 확인후 큐에 push
            if (check.find(make_pair(make_pair(aa, bb), cc)) == check.end()) {
                check.insert(make_pair(make_pair(aa, bb), cc));
                q.push(make_pair(make_pair(aa, bb), cc));
            }
 
        }
        if (b > a) {
            aa = a + a;
            bb = b - a;
            cc = c;
            //같은 수 조합이 나온적 있는지 확인후 큐에 push
            if (check.find(make_pair(make_pair(aa, bb), cc)) == check.end()) {
                check.insert(make_pair(make_pair(aa, bb), cc));
                q.push(make_pair(make_pair(aa, bb), cc));
            }
        }
        if (a > c) {
            aa = a - c;
            cc = c + c;
            bb = b;
            //같은 수 조합이 나온적 있는지 확인후 큐에 push
            if (check.find(make_pair(make_pair(aa, bb), cc)) == check.end()) {
                check.insert(make_pair(make_pair(aa, bb), cc));
                q.push(make_pair(make_pair(aa, bb), cc));
            }
        }
        if (c > a) {
            aa = a + a;
            cc = c - a;
            bb = b;
            //같은 수 조합이 나온적 있는지 확인후 큐에 push
            if (check.find(make_pair(make_pair(aa, bb), cc)) == check.end()) {
                check.insert(make_pair(make_pair(aa, bb), cc));
                q.push(make_pair(make_pair(aa, bb), cc));
            }
        }
        if (b > c) {
            aa = a;
            bb = b - c;
            cc = c + c;
            //같은 수 조합이 나온적 있는지 확인후 큐에 push
            if (check.find(make_pair(make_pair(aa, bb), cc)) == check.end()) {
                check.insert(make_pair(make_pair(aa, bb), cc));
                q.push(make_pair(make_pair(aa, bb), cc));
            }
        }
        if (c > b) {
            aa = a;
            bb = b + b;
            cc = c - b;
            //같은 수 조합이 나온적 있는지 확인후 큐에 push
            if (check.find(make_pair(make_pair(aa, bb), cc)) == check.end()) {
                check.insert(make_pair(make_pair(aa, bb), cc));
                q.push(make_pair(make_pair(aa, bb), cc));
            }
        }
 
 
 
    }
 
    if (pos)cout << 1;
    else cout << 0;
}