[백준] 12886번 돌 그룹

[적용한 알고리즘]

DFS

 

[아이디어]

1500^3 은 너무 크고, 합이 일정하니 (a,b,c) 대신 (a,b) 만 봐줘도 될 것이다.

그럼 1500^2 에 해결이 가능하니 공간을 별로 안잡아 먹는다.

 

x+x가 되는 애는 y 쪽에서 x개를 넘겨주는 거라고 이해하면 되니까

그것만 구현해주면 될 것이다. 

 

[생각의 흐름 / 절차]

[교훈]

은근히 구현이 힘들었다.

시간이나 공간이 부족할 것 같다면 뭐가 일정한지 봐주는 것도 생각해보자.

 

<코드>

#include <cstdio>
#include <algorithm>
using namespace std;
int A, B, C, sum;
bool visited[1501][1501];

void dfs(int x, int y){
    if (visited[x][y]) return;
    visited[x][y] = true;

    int rock[3] = {x, y, sum - (x + y)};

    for (int i = 0; i < 3; i++){
        for (int j = 0; j < 3; j++){
            if (rock[i] < rock[j]){
                int temp[3] = {x, y, sum - (x + y)};
                temp[i] += rock[i];
                temp[j] -= rock[i];
                dfs(temp[0], temp[1]);
            }
        }
    }
}
int main(){
    scanf("%d %d %d", &A, &B, &C);
    sum = A + B + C;

    if (sum % 3 != 0){
        printf("0\n");
        return 0;
    }
    dfs(A, B);

    printf("%d\n", visited[sum / 3][sum / 3]);
    return 0;
}