[백준] 2251 물통

문제

각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부을 수 있는데, 이때에는 한 물통이 비거나, 다른 한 물통이 가득 찰 때까지 물을 부을 수 있다. 이 과정에서 손실되는 물은 없다고 가정한다.

이와 같은 과정을 거치다보면 세 번째 물통(용량이 C인)에 담겨있는 물의 양이 변할 수도 있다. 첫 번째 물통(용량이 A인)이 비어 있을 때, 세 번째 물통(용량이 C인)에 담겨있을 수 있는 물의 양을 모두 구해내는 프로그램을 작성하시오.

입력

첫째 줄에 세 정수 A, B, C가 주어진다.

출력

첫째 줄에 공백으로 구분하여 답을 출력한다. 각 용량은 오름차순으로 정렬한다.

 

DFS를 사용합니다.

#include<bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false),cin.tie(NULL);
#define mset(v) memset(v,0,sizeof(v));
#define rep(i,a) for(int i=0;i<a;++i)
#define REP(i,a) for(int i=1;i<=a;++i)

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef tuple<int, int, int>ti;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
int dy[] = {-1,0,1,0}, dx[] = {0,1,0,-1}, INF = 987654321;

using namespace std;

int A, B, C, v[201][201][201];
vi ans;
void dfs(int a, int b, int c) {
	v[a][b][c] = 1;
	if (!a) {
		ans.push_back(c);
	}
	if (a <= (B - b) && !v[0][a+b][c]) {
		dfs(0, b + a, c);
	}
	if (a >= (B - b) && !v[a-B+b][B][c]) {
		dfs(a - B + b, B, c);
	}
	//a->b
	if (a <= (C - c) && !v[0][b][c+a]) {
		dfs(0, b, c + a);
	}
	if (a >= C - c && !v[a-C+c][b][C]) {
		dfs(a - C + c, b, C);
	}
	//a->c
	if (b >= C - c && !v[a][b-C+c][C]) {
		dfs(a, b - C + c, C);
	}
	if (b <= C - c && !v[a][0][c+b]) {
		dfs(a, 0, c + b);
	}
	//b->c
	if (b <= A - a && !v[a+b][0][c]) {
		dfs(a + b, 0, c);
	}
	if (b >= A - a && !v[A][b-A+a][c]) {
		dfs(A, b - A + a, c);
	}
	//b->a
	if (c >= A - a && !v[A][b][c-A+a]) {
		dfs(A, b, c - A + a);
	}
	if (c <= A - a && !v[a+c][b][0]) {
		dfs(a + c, b, 0);
	}
	//c->a
	if (c <= B - b && !v[a][b+c][0]) {
		dfs(a, b + c, 0);
	}
	if (c >= B - b && !v[a][B][c-B+b]) {
		dfs(a, B, c - B + b);
	}
	//c->b
}
int main() {
	FAST;
	cin >> A >> B >> C;
	dfs(0, 0, C);
	sort(ans.begin(), ans.end());
	for (int r : ans) {
		cout << r << " ";
	}
}