백준 2251: 물통

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
struct info {
	int a, b, c;
};
int A, B, C;
vector<int> v;
bool visited[201][201][201];
void bfs() {
	queue<info> q;
	q.push({ 0,0,C });
	
	while (!q.empty()) {
		int a = q.front().a;
		int b = q.front().b;
		int c = q.front().c;
		q.pop();
		if (visited[a][b][c] == true)continue;
		visited[a][b][c] = true;

		if(a==0)v.push_back(c);

		if (a + b > B)q.push({ a + b - B,B,c });
		else q.push({ 0,a + b,c });

		if (a + c > C)q.push({ a + c - C,b,c });
		else q.push({ 0,b,a + c });

		if (b + a > A)q.push({ A,b + a - A,c });
		else q.push({ b + a,0,c });

		if (b + c > C) q.push({ a,b + c - C,C });
		else q.push({ a,0,b + c });

		if (c + a > A)q.push({ A,b,a + c - A });
		else q.push({ c + a,b,0 });

		if (c + b > B) q.push({ a,B,c + b - B });
		else q.push({ a,c + b,0 });
	}
}
//dfs로 돌렸을 때 멈출 방법이 있낭?

int main() {
	cin >> A >> B >> C;
	bfs();
	sort(v.begin(), v.end());
	for (int i = 0; i < v.size(); i++) {
		cout << v[i] << ' ';
	}
	return 0;
}

물통 성공

 

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

128 MB

10730

5345

3956

50.459%

문제

각각 부피가 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

출처

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

 

골드 5문제지만 쉽진 않았다 . 물을 어떻게 분배할 지 몰라서 고민을 오래했다.

dfs도 생각했지만 dfs보단 bfs가 시간이 빠를 것 같았고 3차원배열로 처리할 생각을 못해서 dfs는 불가능하다고 생각했던 것 같다. 하지만 그런식의 접근이면 bfs도 마찬가지다. 

요새 난이도를 상관없이 잘풀리는 문제도 있고 빨리 안풀리는 문제도 있다. 업솔빙해야겠다.