[Baekjoon/C++] 2251번 - 물통

[백준] Baekjoon Online Judge

문제로 이동

 

문제

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

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

 

입력

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

 

출력

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

 

---

풀이

#include <iostream>
using namespace std;

int A, B, C;
bool check[201][201][201];

void dfs(int a, int b, int c);

void dfs(int a, int b, int c) {
	if (check[a][b][c]) return;

	check[a][b][c] = true;

	dfs(a - min(a, B - b), b + min(a, B - b), c);
	dfs(a - min(a, C - c), b, c + min(a, C - c));
	dfs(a + min(b, A - a), b - min(b, A - a), c);
	dfs(a, b - min(b, C - c), c + min(b, C - c));
	dfs(a + min(c, A - a), b, c - min(c, A - a));
	dfs(a, b + min(c, B - b), c - min(c, B - b));
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> A >> B >> C;

	dfs(0, 0, C);

	for (int i = 0; i <= C; i++) {
		for (int j = 0; j <= B; j++) {
			if (check[0][j][i]) cout << i << ' ';
		}
	}

	return 0;
}

 깊이우선탐색으로 문제를 풀었다.

 

bool check[201][201][201];

void dfs(int a, int b, int c) {
	if (check[a][b][c]) return;

	check[a][b][c] = true;

	dfs(a - min(a, B - b), b + min(a, B - b), c);
	dfs(a - min(a, C - c), b, c + min(a, C - c));
	dfs(a + min(b, A - a), b - min(b, A - a), c);
	dfs(a, b - min(b, C - c), c + min(b, C - c));
	dfs(a + min(c, A - a), b, c - min(c, A - a));
	dfs(a, b + min(c, B - b), c - min(c, B - b));
}

 깊이우선탐색을 구현한 함수이다. 3개 물통의 물을 옮기는 방법은 (a > b), (a > c), (b > a), (b > c), (c > a), (c > b)로 총 6가지이다. 또한 옮겨지는 물의 양은 물을 비우는 물통의 물의 양(a)과 물을 채우는 물통에 남은 용량 (B - b)중 더 작은 것과 같다.