백준 12886 돌 그룹 (C++)

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

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

//a, b의 히스토리
bool visit[1501][1501];

int main(){

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int a, b, c;
    cin>>a>>b>>c;

    int sum=a+b+c;

    if(sum%3){
        cout<<0;
        return 0;
    }

    queue<pair<int, int>> q;

    q.push(make_pair(a, b));
    visit[a][b]=true;

    while(!q.empty()){


        int aa=q.front().first;
        int bb=q.front().second;


        if(aa==bb && aa==sum-aa-bb){
            cout<<1;
            return 0;
        }

        q.pop();

        int stone[3]={aa, bb, sum-aa-bb};


        sort(stone, stone+3);

        //(0, 1), (1, 2), (0, 2) 비교
        for(int i=0;i<3;i++){


            int first;
            int second;

            switch(i){
                case 0:     //0, 1
                    first=stone[0]*2;
                    second=stone[1]-stone[0];
                    break;
                case 1:     //1, 2
                    first=stone[0];
                    second=stone[1]*2;
                    break;
                case 2:     //0, 2
                    first=stone[0]*2;
                    second=stone[1];
                    break;

            }


            if(!visit[first][second]){
                visit[first][second]=true;
                q.push(make_pair(first, second));
            }
                    
                

            
        }
    }


    cout<<0;
    

    
    return 0;
}

1. 문제

오늘 강호는 돌을 이용해 재미있는 게임을 하려고 한다. 먼저, 돌은 세 개의 그룹으로 나누어져 있으며 각각의 그룹에는 돌이 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을 출력한다.

2. 풀이

    int a, b, c;
    cin>>a>>b>>c;

    int sum=a+b+c;

    if(sum%3){
        cout<<0;
        return 0;
    }

 

돌의 개수는 0 이상의 정수이므로 3으로 나누어 떨어지지 않는다면 세 돌을 같게 만들 수 없다.

    //a, b의 히스토리
    bool visit[1501][1501];

    queue<pair<int, int>> q;

    q.push(make_pair(a, b));
    visit[a][b]=true;

visit[i][j]: 세 돌 중 두 개의 돌이 i, j의 개수일 때를 방문했는 지 이다. 연산은 3개 중 두 개의 돌을 골라 작은 돌을 두배 하고, 작은 돌의 수 만큼 큰 돌에서 빼므로 전체 돌의 개수는 항상 같다. 따라서 총 돌의 개수에서 a, b를 뺀 값이 나머지 c의 값이다.

        int aa=q.front().first;
        int bb=q.front().second;


        if(aa==bb && aa==sum-aa-bb){
            cout<<1;
            return 0;
        }

세 돌의 개수가 같다면 1을 출력하고 프로그램을 종료한다.

        int stone[3]={aa, bb, sum-aa-bb};


        sort(stone, stone+3);

        //(0, 1), (1, 2), (0, 2) 비교
        for(int i=0;i<3;i++){


            int first;
            int second;

            switch(i){
                case 0:     //0, 1
                    first=stone[0]*2;
                    second=stone[1]-stone[0];
                    break;
                case 1:     //1, 2
                    first=stone[0];
                    second=stone[1]*2;
                    break;
                case 2:     //0, 2
                    first=stone[0]*2;
                    second=stone[1];
                    break;

            }


            if(!visit[first][second]){
                visit[first][second]=true;
                q.push(make_pair(first, second));
            }
                    
                

            
        }

세 돌의 개수를 저장하고, 크기에 따른 연산 방법이 다르므로 돌의 개수를 정렬해준다. 그렇게 되면 아래 3가지 케이스의 연산을 할 수 있다.

• 0번째 돌과 1번째 돌: 0번째 돌에 두 배를 하고, 1번째 돌에서 0번째 돌을 뺀다.
• 1번째 돌과 2번째 돌: 0번째 돌은 연산에 관여하지 않는다. 1번째 돌에 2배를 하면 2번째 돌은 자동으로 결정이 된다.
• 0번째 돌과 2번째 돌: 0번째 돌에 두 배를 하고, 1번째 돌은 연산하지 않는다. 2번째 돌의 개수는 자동으로 결정된다.

연산이 끝나고 해당 케이스를 방문한 적이 있는지 확인하여 BFS를 돌린다. 다 돌았음에도 세 돌의 개수가 같은 케이스가 존재하지 않았다면 0을 출력하고 프로그램을 종료한다.