[12886번] 돌 그룹

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

12886번: 돌 그룹

돌 그룹 3가지가 있는데 이 3가지 그룹의 돌 개수를 같게 할 수 있는지를 찾는 문제입니다.

각 그룹의 돌 개수를 정점이라고 생각하면 BFS로 풀 수 있습니다.

점화식은 d[a][b][c]로 정할 수 있는데, 전체 돌 개수를 구한 sum = a + b + c 값을 이용하면 굳이 3차원 배열이 아닌 d[a][b]인 2차원 배열으로도 문제를 해결 할 수 있습니다.

 

점화식 d[i][j] : 첫 번째 그룹의 돌의 수 i개, 두 번째 그룹의 돌의 수가 j개를 만들 수 있으면 true, 아직 만든 적이 없다면 false로 저장을 합니다.

BFS를 하기전에 sum을 3으로 나누어 떨어지지 않는다면 세 그룹의 돌 개수가 같아질 수 없으므로 그냥 0을 출력하고 종료합니다.

큐에 정점의 정보를 넣을 때는 세번째 그룹은 연산으로 처리가 가능하기 때문에 2개의 그룹의 돌 개수만 넣습니다.

정답은 모든 돌 개수가 sum/3인 정점을 방문해야 하므로 d[sum/3][sum/3]에 있습니다.

 

[코드]

#include <iostream>
#include <queue>
using namespace std;
bool d[1501][1501];
int sum;
int main () {
    int a, b, c;
    cin >> a >> b >> c;
    sum = a + b + c;
    if (sum % 3 != 0) {
        cout << 0 << '\n';
        return 0;
    }
    queue<pair<int, int>> q;
    q.push(make_pair(a, b));
    d[a][b] = true;
    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        int z = sum - x - y;
        if (x > y) {
            x = x - y;
            y = y + y;
            if (d[x][y]) continue;
            q.push(make_pair(x, y));
            d[x][y] = true;
        } else if (x < y) {
            y = y - x;
            x = x + x;
            if (d[x][y]) continue;
            q.push(make_pair(x, y));
            d[x][y] = true;
        }
        if (x > z) {
            x = x - z;
            z = z + z;
            if (d[x][sum - x - z]) continue;
            q.push(make_pair(x, sum - x - z));
            d[x][sum - x - z] = true;
        } else if (x < z){
            z = z - x;
            x = x + x;
            if (d[x][sum - x - z]) continue;
            q.push(make_pair(x, sum - x - z));
            d[x][sum - x - z] = true;
        }
        if (y > z) {
            y = y - z;
            z = z + z;
            if (d[x][sum - y - z]) continue;
            q.push(make_pair(sum - y - z, y));
            d[sum - y - z][y] = true;
        } else if (z < y) {
            y = y - z;
            z = z + z;
            if (d[x][sum - y - z]) continue;
            q.push(make_pair(sum - y - z, y));
            d[sum - y - z][y] = true;
        }
    }
    if (d[sum/3][sum/3]) {
        cout << 1 << '\n';
    } else {
        cout << 0 << '\n';
    }
    return 0;
}

[결과]

1 1 2 //input
0 //output