백준 2251번 물통 - C++ 풀이

---

 

1. 모든 상황의 경우의 수는 200*200*200가지이다.
2. 각 상황에서 x물통에서 y물통으로 물을 붓는 모든 경우를 시도하면서 가능한 상황을 모두 구해준다.

 

1. 모든 상황의 경우의 수는 200*200*200가지이다.

 각 물통의 최대 용량은 200이므로 세 물통에 물이 담기는 경우의 수는 N^3가지이다.

 

2. 각 상황에서 x물통에서 y물통으로 물을 붓는 모든 경우를 시도하면서 가능한 상황을 모두 구해준다.

 DFS를 이용하여 계속해서 물을 붓는 시뮬레이션을 해준다. DFS(a, b, c) = 현재 세 물통에 a, b, c리터의 물이 담겨있는 상황이라고 하자. 현재 상황에서 물을 붓는 경우는 a -> b, a -> c, b -> a, b -> c, c -> a, c -> b로 총 6가지 이다. 각 경우에 대해 물을 붓고 난 다음의 각각의 물의 양 a', b', c'에 대해 DFS(a', b', c')을 재귀적으로 호출해주면 된다.

 이때 이미 계산한 상황에 대해서는 또 계산할 필요가 없으므로 visit 배열을 이용하여 해당 상황에 방문한 이력이 있음을 관리해준다. 따라서 전체 시간복잡도는 O(6N^3)

 

반응형

---

#include <iostream>
#include <string.h>

using namespace std;

const int MAX = 201;

int A, B, C;
int visit[MAX][MAX][MAX];

struct Bottle {
    int capacity, water;
};

// pour(x, y): x에서 y로 붓는다.
pair<Bottle, Bottle> pour(Bottle x, Bottle y) {
    int diff = min(y.capacity-y.water, x.water);
    x.water -= diff;
    y.water += diff;
    
    return {x, y};
}

void DFS(Bottle a, Bottle b, Bottle c) {
    if (visit[a.water][b.water][c.water]) return;
    visit[a.water][b.water][c.water] = true;
    
    pair<Bottle, Bottle> ab = pour(a, b);
    DFS(ab.first, ab.second, c);
    
    pair<Bottle, Bottle> ac = pour(a, c);
    DFS(ac.first, b, ac.second);
    
    pair<Bottle, Bottle> ba = pour(b, a);
    DFS(ba.second, ba.first, c);
    
    pair<Bottle, Bottle> bc = pour(b, c);
    DFS(a, bc.first, bc.second);
    
    pair<Bottle, Bottle> ca = pour(c, a);
    DFS(ca.second, b, ca.first);
    
    pair<Bottle, Bottle> cb = pour(c, b);
    DFS(a, cb.second, cb.first);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> A >> B >> C;
    
    DFS({A, 0}, {B, 0}, {C, C});
    
    for (int i=0; i<=C; i++) {
        for (int j=0; j<=B; j++) {
            if (visit[0][j][i]) {
                cout << i << " ";
                break;
            }
        }
    }

    return 0;
}