물통

https://www.acmicpc.net/problem/2251

문제

각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다.

처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다.

이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부을 수 있는데,

이때에는 한 물통이 비거나, 다른 한 물통이 가득 찰 때까지 물을 부을 수 있다.

이 과정에서 손실되는 물은 없다고 가정한다.

이와 같은 과정을 거치다보면 세 번째 물통(용량이 C인)에 담겨있는 물의 양이 변할 수도 있다.

첫 번째 물통(용량이 A인)이 비어 있을 때,

세 번째 물통(용량이 C인)에 담겨있을 수 있는 물의 양을 모두 구해내는 프로그램을 작성하시오.

입력

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

출력

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

예제 입력 1

8 9 10

예제 출력 1

1 2 8 9 10

출처

Olympiad > USA Computing Olympiad > 2000-2001 Season > USACO Winter 2001 Contest > Orange 4번

• 문제의 오타를 찾은 사람: kesakiyo
• 데이터를 추가한 사람: methylene

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색
• 깊이 우선 탐색

통과된 코드

#include <iostream>
using namespace std;
int _A, _B, _C;
bool _Check[201][201][201];
bool _Numbers[201];

void DFS(int _a, int _b, int _c)
{
	if (_a == 0) {
		_Check[_a][_b][_c] = true;
		_Numbers[_c] = true;
	}
	int  _tA, _tB, _tC;
	if (_a != 0) {
		_tB = _a + _b;
		if (_tB > _B) {
			_tA = _tB - _B;
			_tB = _B;
		}
		else _tA = 0;
		if (!_Check[_tA][_tB][_c]) {
			_Check[_tA][_tB][_c] = true;
			DFS(_tA, _tB, _c);
		}
			
		_tC = _a + _c;
		if (_tC > _C) {
			_tA = _tC - _C;
			_tC = _C;
		}
		else _tA = 0;
		if (!_Check[_tA][_b][_tC]) {
			_Check[_tA][_b][_tC] = true;
			DFS(_tA, _b, _tC);
		}
	}

	if (_b != 0) {
		_tA = _b + _a;
		if (_tA > _A) {
			_tB = _tA - _A;
			_tA = _A;
		}
		else _tB = 0;
		if (!_Check[_tA][_tB][_c]) {
			_Check[_tA][_tB][_c] = true;
			DFS(_tA, _tB, _c);
		}

		_tC = _b + _c;
		if (_tC > _C) {
			_tB = _tC - _C;
			_tC = _C;
		}
		else _tB = 0;
		if (!_Check[_a][_tB][_tC]) {
			_Check[_a][_tB][_tC] = true;
			DFS(_a, _tB, _tC);
		}
	}

	if (_c != 0) {
		_tA = _c + _a;
		if (_tA > _A) {
			_tC = _tA - _A;
			_tA = _A;
		}
		else _tC = 0;
		if (!_Check[_tA][_b][_tC]) {
			_Check[_tA][_b][_tC] = true;
			DFS(_tA, _b, _tC);
		}

		_tB = _c + _b;
		if (_tB > _B) {
			_tC = _tB - _B;
			_tB = _B;
		}
		else _tC = 0;
		if (!_Check[_a][_tB][_tC]) {
			_Check[_a][_tB][_tC] = true;
			DFS(_a, _tB, _tC);
		}
	}


}


int main()
{
	cin >> _A >> _B >> _C;
	_Check[0][0][_C];
	_Numbers[_C];
	DFS(0, 0, _C);
	for (int i = 0; i <= _C; i++)
		if (_Numbers[i])
			cout << i << " ";

	return 0;
}