취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 2251번 문제인 물통이다.
문제는 아래 링크를 확인하자.

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

현재 존재하는 물통의 상태에서 다음 상태로 가능한(각 물통을 들어 다른 물통에 붓는 행동) 상태 중 아직 탐색 시작을 하지 않은 상태를 계속 탐색해나가는 것으로 문제를 해결해나갈 수 있다.

"A물통이 비어있을 때의" 가능한 C물통의 물의 양을 출력해야함에 유의하자.

0 또한 C물통의 가능한 물의 양임을 놓치지 말자.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int A, B, C;
bool ans[201];
int visited[201][201][201];

void func(int a, int b, int c) {
	visited[a][b][c] = 1;
	if (a == 0) ans[c] = 1;
	int d = min(a, B - b);
	if (!visited[a - d][b + d][c]) func(a - d, b + d, c);
	d = min(a, C - c);
	if (!visited[a - d][b][c + d]) func(a - d, b, c + d);
	d = min(b, A - a);
	if (!visited[a + d][b - d][c]) func(a + d, b - d, c);
	d = min(b, C - c);
	if (!visited[a][b - d][c + d]) func(a, b - d, c + d);
	d = min(c, A - a);
	if (!visited[a + d][b][c - d]) func(a + d, b, c - d);
	d = min(c, B - b);
	if (!visited[a][b + d][c - d]) func(a, b + d, c - d);
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> A >> B >> C;
	func(0, 0, C);

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