글 읽기 - 2251번 반례....

jinuu1208 6년 전 0

2251번 반례가 어떤게 있을까요?? ..

중간 과정을 출력해봐도, 문제를 못찾겠네요 ㅜ c가 0인 경우도 출력되구요..

고수님들 부탁드립니다 ..

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <map>

using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);

	int a, b, c;
	cin >> a >> b >> c;// 전체 물의 양 : c
	int total = c;

	pair<int, int> now, next;
	now = { 0,0 };
	queue<pair<int, int>> q;
	q.push(now);
	// chk: chk, d:dist
	map<pair<int, int>, int> chk;
	chk[now] = 1;
	map<pair<int, int>, int> d;
	d[now] = 0;

	int tmp = 0; // 이동시키는 물의 양
	int now_a, now_b, now_c;
	vector<int> ans;
	while (!q.empty())
	{
		now = q.front();
		q.pop();

		now_a = now.first;
		now_b = now.second;
		now_c = total-(now.first+ now.second);

		//cout << "a:"<<now_a << "b:" << now_b<<"c:" << now_c<<'\n';

		if (now_a == 0) ans.push_back(now_c);

		if ((now_a>=0)&& (now_b>=0)&& (now_c>=0))
		{
			// 1. a->b
			next = { 0,0 };
			if (now_a >= (b - now_b))
			{
				tmp = b - now_b;
				next.first = now_a - tmp;
				next.second = b;
			}
			else
			{
				tmp = now_a;
				next.first = 0;
				next.second = now_b + now_a;
			}
			if ((chk[next] == 0) && ((next.first+next.second)<=total))
			{
				q.push(next);
				chk[next] = 1;
				d[next] = d[now] + 1;
			}

			// 2. a->c
			next = { 0,0 };
			if (now_a >= c - now_c)
			{
				tmp = c - now_c;
				next.first = now_a - tmp;
				//next = c;
			}
			else
			{
				tmp = now_a;
				next.first = 0;
				//next_c = now_c + now_a;
			}
			if ((chk[next] == 0) && ((next.first + next.second) <= total))
			{
				q.push(next);
				chk[next] = 1;
				d[next] = d[now] + 1;
			}

			// 3. b->a
			next = { 0,0 };
			if (now_b >= a - now_a)
			{
				tmp = a - now_a;
				next.second = now_b - tmp;
				next.first = a;
			}
			else
			{
				tmp = now_b;
				next.second = 0;
				next.first = now_a + tmp;
			}
			if ((chk[next] == 0) && ((next.first + next.second) <= total))
			{
				q.push(next);
				chk[next] = 1;
				d[next] = d[now] + 1;
			}

			// 4. b->c
			next = { 0,0 };
			if (now_b >= c - now_c)
			{
				tmp = c - now_c;
				next.second = now_b - tmp;
				//next_c = c;
			}
			else
			{
				tmp = now_b;
				next.second = 0;
				//next_c = now_c + tmp;
			}
			if ((chk[next] == 0) && ((next.first + next.second) <= total))
			{
				q.push(next);
				chk[next] = 1;
				d[next] = d[now] + 1;
			}

			// 5. c->a
			next = { 0,0 };
			if (now_c >= a - now_a)
			{
				tmp = a - now_a;
				//next_c = now_c - tmp;
				next.first = a;
			}
			else
			{
				tmp = now_c;
				//next_c = 0;
				next.first = now_a + tmp;
			}
			if ((chk[next] == 0) && ((next.first + next.second) <= total))
			{
				q.push(next);
				chk[next] = 1;
				d[next] = d[now] + 1;
			}
			// 6. c->b
			next = { 0,0 };
			if (now_c >= b - now_b)
			{
				tmp = b - now_b;
				//next_c = now_c - tmp;
				next.second = b;
			}
			else
			{
				tmp = now_c;
				//next_c = 0;
				next.second = now_b + tmp;
			}
			if ((chk[next] == 0) && ((next.first + next.second) <= total))
			{
				q.push(next);
				chk[next] = 1;
				d[next] = d[now] + 1;
			}
		}
		
	}

	// print ans
	sort(ans.begin(), ans.end());
	for (auto it = ans.begin(); it != ans.end(); it++)
		cout << (*it) << ' ';
	cout << '\n';
	

	//system("pause");
	return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

2251번 반례....

jinuu1208 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말