BOJ 2251 물통

사용한 알고리즘

DP, DFS

알고리즘 설명

물통 A,B와 C를 이용하여 만들수 있는 물의 양 종류를 출력해야한다.
여기서 항상 A+B+C의 물의 양은 항상 같으므로 두 물통에 있는 물에 양으로 나머지 하나의 물의 양을 표현할 수 있다.
물을 옮기는 방법은 3!로 총 6가지의 방법이 있다.
A->B, A->C, B->A, B->C, C->A, C->B
이때에 dp에 물통 B의 물의 양와 물통 C의 물의 양을 state로 나타내어 memoization를 진행한다.
위 6가지 케이스로 탐색을 시작하는데 물통 B와 물통 C에 대한 탐색을 한번씩만 진행하도록 한다.
각 DFS에서 물통 a에 물이 없는 경우 물통 C에 있는 물의 양을 저장한다.
모든 탐색이후 가능한 물통 C에 있는 물의 양을 출력한다.

풀이

// baekjoon 2251 yechan
#include <cstdio>
#include <algorithm>
#include <queue>
#include <utility>
using namespace std;
typedef pair<int, int> P;
const int MAX_C=201;

int A, B, C;
bool visited[MAX_C][MAX_C];
bool possible[MAX_C];

void dfs(int a, int b, int c) {
	visited[b][c]=true;

	if (a == 0) possible[c]=true;

	// 1. A -> B
	if (!visited[min(a+b, B)][c]) dfs(max(a-B+b, 0), min(a+b, B), c);

	// 2. A -> C
	if (!visited[b][a+c]) dfs(0, b, a+c);

	// 3. B -> A
	if (!visited[max(0, b-A+a)][c]) dfs(min(A, a+b), max(0, b-A+a), c);

	// 4. B -> C
	if (!visited[0][b+c]) dfs(a, 0, b+c);

	// 5. C -> A
	if (!visited[b][max(0, c-A+a)]) dfs(min(A,a+c), b, max(0, c-A+a));

	// 6. C -> B
	if (!visited[min(B, c+b)][max(0, c-B+b)]) dfs(a, min(B, c+b), max(0, c-B+b));
}

	int main() {
	scanf("%d%d%d", &A, &B, &C);
	possible[C]=true;

	dfs(0, 0, C);

	for (int i=0; i<=C; i++)
		if (possible[i])
			printf("%d ", i);
	puts("");

	return 0;
}