[백준 2251번] 물통 풀이

2251번: 물통

 

담을 수 있는 부피가 각각 A, B, C 인 물통 3개가 있다. 초기에는 마지막 물통만 가득 차 있으며, 나머지 물통은 비어있다. 한 물통이 가득 차거나 빌 때까지 물을 옮기고, 이를 반복할 수 있다. 처음 물통에 들어있는 양이 0 일 때, 마지막 물통에 들어있을 수 있는 물의 양을 모두 구해야 한다.

 

가장 쉬운 방법은, 각 물통에 담길 수 있는 물의 양에 대해 모든 경우의 수를 탐색하고, 첫번째 물통이 비었다면 마지막 물통의 양을 저장하는 것이다.

 

// 부피가 A인 물통에 a, 부피가 B인 물통에 b, 부피가 C인 물통에 c만큼 들어있는 경우에 대해 a == 0 인지 확인

void solve(int a, int b, int c) {

    if (a == 0) v.push_back(c);

}

 

이후, 물통에 있는 물을 다른 물통으로 옮겨 다음 경우의 수를 확인한다. 이 때,  물을 옮길 수 있는 방법은 6가지가 있다.

 

부피 A 물통 -> 부피 B 물통 

부피 A 물통 -> 부피 C 물통

부피 B 물통 -> 부피 A 물통 

부피 B 물통 -> 부피 C 물통 

부피 C 물통 -> 부피 A 물통

부피 C 물통 -> 부피 B 물통

 

따라서 옮기는 물의 양을 적절히 계산하여 각각의 물통에서 빼고, 더하면 재귀적으로 모든 경우의 수를 확인할 수 있다.

 

void solve(int a, int b, int c) {

    if (a == 0) v.push_back(c);
    
    solve(a-B물통에옮기는양, b+A물통으로부터얻는양, c)
    solve(a-C물통에옮기는양, b, c+A물통으로부터얻는양)
    solve(a+B물통으로부터얻는양, b-A물통에옮기는양, c)
    solve(a, b-C물통에옮기는양, c+B물통으로부터얻는양)
    solve(a+C물통으로부터얻는양, b, c-A물통에옮기는양)
    solve(a, b+C물통으로부터얻는양, c-B물통에옮기는양)
    return ;
}

 

물통에서 물통으로 옮기는 물을 양은 give() 함수를 통해 구한다. 만약 fBot 부피의 물통에 들어있는 물 from을 다 옮겼을 때 tBot 부피의 물통이 넘친다면, tBot 물병에서 받을 수 있는 물의 양(tBot - to) 만큼만 옮긴다. 반면, fBot 물통에 들어있는 물을 다 옮겨도 넘치지 않는다면 from을 전부 옮긴다.

 

// 부피 fBot 물통에 들어있는 물의양 from
// 부피 tBot 물통에 들어있는 물의양 to
// 물은 fBot 물통에서 tBot 물통으로 이동

int give(int from, int fBot, int to, int tBot) {

    if ((to+from) > tBot) return (tBot - to);
    return from;
}

 

solve() 함수에 옮기는 물의 양을 구하는 함수 give()를 결합하면, 다음과 같다. 만약, 이전에 a, b, c 조합을 확인한 적이 있다면 이 이후에 물병을 옮기는 모든 경우의 수도 이미 확인한 조합이다. 따라서 a, b, c 조합을 확인할 때마다 check[a][b][c]에 기록하고 만약 이전에 체크한 조합을 다시 확인해야 하는 경우라면 함수를 종료한다.

 

void solve(int a, int b, int c) {

    if (check[a][b][c]) return;
    check[a][b][c] = true;

    if (a == 0) v.push_back(c);
    solve(a-give(a, A, b, B), b+give(a, A, b, B), c);
    solve(a-give(a, A, c, C), b, c+give(a, A, c, C));
    solve(a+give(b, B, a, A), b-give(b, B, a, A), c);
    solve(a, b-give(b, B, c, C), c+give(b, B, c, C));
    solve(a+give(c, C, a, A), b, c-give(c, C, a, A));
    solve(a, b+give(c, C, b, B), c-give(c, C, b, B));
    return ;
}

 

문제에서는 저장한 c의 값을 오름차순으로 출력하라고 요구하였으므로, c 값들이 들어있는 벡터를 정렬하여 출력한다.

 

sort(v.begin(), v.end());
for (int i=0; i<v.size(); i++)
	printf("%d ", v[i]);

 

전체 코드는 다음과 같다.

 

#include <iostream>
#include <cstdio>
#include <algorithm> 
#include <cstring>
#include <vector>
#include <cmath>
#include <tuple>
#include <queue>

using namespace std;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;

int A, B, C;
bool check[201][201][201];
vector<int> v;

int give(int from, int fBot, int to, int tBot) {
    
    if ((to+from) > tBot) return (tBot - to);
    return from;
}

void solve(int a, int b, int c) {

    if (check[a][b][c]) return;
    check[a][b][c] = true;

    if (a == 0) v.push_back(c);
    solve(a-give(a, A, b, B), b+give(a, A, b, B), c);
    solve(a-give(a, A, c, C), b, c+give(a, A, c, C));
    solve(a+give(b, B, a, A), b-give(b, B, a, A), c);
    solve(a, b-give(b, B, c, C), c+give(b, B, c, C));
    solve(a+give(c, C, a, A), b, c-give(c, C, a, A));
    solve(a, b+give(c, C, b, B), c-give(c, C, b, B));
    return ;
}

int main() {

    scanf("%d %d %d", &A, &B, &C);
    memset(check, false, sizeof(check));

    solve(0, 0, C);
    sort(v.begin(), v.end());
    for (int i=0; i<v.size(); i++)
        printf("%d ", v[i]);
    return 0;
}