[ 백준 / C++ ] 2251 : 물통

[ 문제 ]

 

2251번: 물통

 

[ 접근방법 ]

 

가능한 경우의 수가 최대 200^3 이므로 브루트포스로 모든 경우를 확인하였다.

 

A→B, A→C, B→A, B→C, C→A, C→B 순으로 재귀를 통해 확인하였고, 

각각 물을 전부 옮길 수 있거나 아닌 경우로 나누어 진행하였다.

 

최대 12개의 가지가 뻗어나가지만 chk 배열을 통해 중복을 체크하고 있기 때문에 상관없다.

 

[ 소스코드 ]

 

#include <iostream>

using namespace std;

int a, b, c;
bool ans[205], chk[205][205][205];

void f(int x, int y, int z){
    if(chk[x][y][z]) return;

    chk[x][y][z] = true;

    if(!x) ans[z] = true;

    if(x && y < b){
        if(x < (b - y)) f(0, x + y, z);
        else f(x - (b - y), b, z);
    }
    if(x && z < c){
        if(x < (c - z)) f(0, y, x + z);
        else f(x - (c - z), y, c);
    }
    if(y && x < a){
        if(y < (a - x)) f(x + y, 0, z);
        else f(a, y - (a - x), z);
    }
    if(y && z < c){
        if(y < (c - z)) f(x, 0, y + z);
        else f(x, y - (c - z), c);
    }
    if(z && x < a){
        if(z < (a - x)) f(x + z, y, 0);
        else f(a, y, z - (a - x));
    }
    if(z && y < b){
        if(z < (b - y)) f(x, y + z, 0);
        else f(x, b, z - (b - y));
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> a >> b >> c;

    f(0, 0, c);

    for(int i = 0; i <= 200; i++){
        if(ans[i]){
            cout << i << " ";
        }
    }

    return 0;
}