백준 12886

이 문제를 처음 봤을 때는 다른 그래프 순회처럼 check 변수를 별 생각 없이 사용하여 문제를 풀고자 하였다.

그런데 check 배열을 선언하고자 하니 [1501][1501][1501]로 1501*1501*1501*1byte = 3234MB정도 나오는게 아닌가..

택도 없다.

그럼 어떻게 배열을 줄일까?

우리는 세가지 변수 A, B, C를 받고 이는 임의의 수이므로 크기순으로 정렬을 하여도 문제의 답에는 영향을 전혀 주지 않는다.

그럼 이를 정렬한 세가지 값으로 max, mid, min이라 가정하였을 때, 그리고 A, B, C의 값의 합을 sum이라 하였을 때,

sum = max + mid + min 으로 항상 같고 이는 곧 sum - max - min = mid라는 식 또한 만들 수 있다.

여기서 우리는 max와 min의 값을 알 경우 세 값의 조합(check 배열을 쓰기 위한)은 항상 동일하게 유지된다는 것을 알 수 있다.

(부가적으로, 문제에서 사용되는 식이 {bigger-smaller, smaller+smaller, nothing} 으로 두개의 값에 항상 하나는 작은 것을 빼고 하나는 작은 것을 더함으로 sum의 값이 항상 유지된다는 것을 명심하자.)

그로므로 check 배열은 [1501][1501][1501]의 사이즈가 아닌 [1501][1501]만으로도 검사했던 수열인지 확인할 수 있는 것이다.

아래는 내 코드이다.

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

class num{
public:
    int a[3];
    num(){}
    num(int A, int B, int C){
        a[0] = A; a[1] = B; a[2] = C;
        sort(a, a+3);
    }
};

bool check[1501][1501];
num n;

pair<int, int> cal(int x, int y){
    return make_pair(x+x, y-x);
}

bool go(){
    queue<num> q;
    q.push(n);
    check[n.a[0]][n.a[2]] = true;
    while(!q.empty()){
        num node = q.front(); q.pop();
        if(node.a[0] == node.a[1] && node.a[1] == node.a[2]) return true;
        pair<int, int> p;
        if(node.a[0] != node.a[1]){
            p = cal(node.a[0], node.a[1]);
            num next(p.first, p.second, node.a[2]);
            if(!check[next.a[0]][next.a[2]]) {
                q.push(next);
                check[next.a[0]][next.a[2]] = true;
            }
        }
        if(node.a[1] != node.a[2]){
            p = cal(node.a[1], node.a[2]);
            num next(node.a[0], p.first, p.second);
            if(!check[next.a[0]][next.a[2]]) {
                q.push(next);
                check[next.a[0]][next.a[2]] = true;
            }
        }
        if(node.a[0] != node.a[2]){
            p = cal(node.a[0], node.a[2]);
            num next(node.a[1], p.first, p.second);
            if(!check[next.a[0]][next.a[2]]) {
                q.push(next);
                check[next.a[0]][next.a[2]] = true;
            }
        }
    }
    return false;
}

int main(){
    int a, b, c;
    cin >> a >> b >> c;
    n = num(a, b, c);
    bool result = go();
    if(result) cout << 1;
    else cout << 0;
    return 0;
}