글 읽기 - 반례가 있을런지요!? 힌트라도 말씀해주시면 감사하겠습니다.

park780172 5년 전 0

또 문제에서 막히네요 ㅠㅠ

저는 BFS로 구현해보았고

생각해본 예제들은 다 맞게 출력 되는 것 같은데

계속 제출하자마자 틀렸습니다가 나오네요..

반례나 힌트, 코드 지적 말씀해주시면 정말 감사하겠습니다!

코드의 맨 위 주석에 제가 입력해보았던 예제들도 있습니다.

BFS 안에 코드가 긴 이유는

현재 채널이 A인지 B인지 따로 구현해서 그렇습니다!

저도 반례를 계속 찾아 보고 있습니다!

/*
입력
7
144.000 144.020 A 146.000
144.000 144.020 B 146.000
144.000 144.020 A 144.000
144.000 145.080 A 145.100
144.000 145.080 B 145.100
144.020 146.000 A 144.100
144.020 146.000 A 144.120

출력
1
2
0
2
1
4
5
*/

#include <iostream>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
#include <map>

using namespace std;

double A = 0.0, B = 0.0, goal = 0.0;

char now;

int BFS()
{
	queue<pair<int, char> > q;

	bool visit[2002] = { false, };

	memset(visit, false, sizeof(visit));

	// 현재 채널에 따라 경우의 수가 2가지로 나눌 수 있다.
	if (now == 'A')
	{
		q.push({ (int)A, now });
		visit[(int)A] = true;

	}
	else if (now == 'B')
	{
		q.push({ (int)B, now });
		visit[(int)B] = true;
	}

	int ret = 0;

	while (!q.empty())
	{
		int qSize = q.size();

		while (qSize--)
		{
			int present = q.front().first;
			char aorb = q.front().second;

			int var = present;
			// 밑에 연산에 의해 present가 변하므로, var을 활용한다.

			q.pop();

			if (present == (int)goal)
			{
				// 같으면 return
				return ret;
			}

			if (aorb == 'A')
			{
				// A/B
				aorb = 'B';
				present = (int)B;
				if (!visit[present])
				{
					q.push({ present, aorb });
					visit[present] = true;
				}

				// up
				aorb = 'A'; // 단순 up을 누르는 것이므로, 위와 달리 aorb = 'A'로 다시 설정
				present = var; // 초기 present를 저장해놨던 var 활용.(연산에 의해 변할 수 있기 때문)
				present += 20; // up은 +20
				if (present > 2000) present = 0; 
				// 146.000(= 2000)을 초과하면, 그 반대편인 144.000(=0)으로 초기화.
				if (!visit[present])
				{
					// 방문하지 않았다면

					q.push({ present, aorb });
					visit[present] = true;
				}

				// down
				aorb = 'A';
				present = var;
				present -= 20;
				if (present < 0) present = 2000;
				if (!visit[present])
				{
					q.push({ present, aorb });
					visit[present] = true;
				}
			}
			else if (aorb == 'B')
			{
				// A/B
				aorb = 'A';
				present = (int)A;
				if (!visit[present])
				{
					q.push({ present, aorb });
					visit[present] = true;
				}

				// up
				aorb = 'B';
				present = var;
				present += 20;
				if (present > 2000) present = 0;
				if (!visit[present])
				{
					q.push({ present, aorb });
					visit[present] = true;
				}

				// down
				aorb = 'B';
				present = var;
				present -= 20;
				if (present < 0) present = 2000;
				if (!visit[present])
				{
					q.push({ present, aorb });
					visit[present] = true;
				}
			}
		}

		++ret;

		// 어차피 최댓값이 6이므로, 6이상이 되면, 바로 return.
		if (ret >= 6) return ret;
	}
}

int main(void)
{
	int T = 0;

	scanf("%d", &T);

	for (int i = 0; i < T; i++)
	{
		scanf("%lf %lf %c %lf", &A, &B, &now, &goal);

		/*
		144.000 이상 ~ 146.000 이하이므로

		곱하기 1000을 하면
		144000 이상 ~ 146000이하

		빼기 144000
		0 이상 ~ 2000 이하 이므로,

		bool visit[2002]을 쉽게 이용할 수 있다.
		*/

		A *= 1000;
		B *= 1000;
		goal *= 1000;

		A -= 144000;
		B -= 144000;
		goal -= 144000;

		int result = BFS();

		// 6번까지가 최대이다. 어차피 6 이상은 번호를 직접 6개를 누를 수 있기 때문이다.
		if (result >= 6) printf("6\n");
		else printf("%d\n", result);
	}
	
	return 0;
}

park780172 5년 전 0

@mulijoa

감사합니다. 해결하였습니다.

문제를 제대로 안 읽었네요...

세 가지 전략 중에서 하나를 선택하여 이루어진다.

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

문제

문제

출처

ICPC

반례가 있을런지요!? 힌트라도 말씀해주시면 감사하겠습니다.

park780172 5년 전 0

park780172 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말