글 읽기 - 시간초과... 고수님들 부탁드려요

jinuu1208 6년 전 0

bfs 기반으로 풀었습니다.

특별히 오래걸릴 부분이 없어 보이는데.. 어디가 오래 걸려서 시간 초과일까요 ? ㅜㅜ

고수님들 부탁드립니다.

#include <iostream>
#include <queue>
#include <algorithm>
#include <string>
#include <vector>
#define MAX 10000
using namespace std;

int shift(int a, int flag)// left, right shifting 함수
{
	ios_base::sync_with_stdio(false);

	string s = to_string(a);
	string tmp = s;
	if (flag == 1)// left case
	{
		for (int i = 0; i < s.length() - 1; i++)
		{
			s[i] = s[i + 1];
		}
		s[s.length() - 1] = tmp[0];
	}
	else if (flag == 0)// right case
	{
		for (int i = 0; i < s.length() - 1; i++)
		{
			s[s.length() - 1 - i] = s[s.length() - 1 - i + 1];
		}
		s[0] = tmp[s.length() - 1];
	}
	//cout << s << '\n';
	int out = stoi(s);
	return out;
}

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

	int t;
	cin >> t;

	for (int i = 0; i < t; i++)
	{
		int a, b;
		cin >> a >> b;

		// init q
		queue<int> q;
		q.push(a);

		int chk[MAX] = { 0, }, d[MAX] = { 0, }; // chk : 해당 위치 접근 여부, d : 해당 위치 접근을 위한 단계
		vector<string> v(MAX);
		int from[MAX];

		from[a] = 0;
		chk[a] = 1;
		d[a] = 0;

		while (!q.empty())
		{
			int now = q.front();
			q.pop();

			// D, N->2*N
			if (2 * now < MAX)
			{
				int next = 2 * now;
				if (chk[next] == 0)
				{
					q.push(next);
					chk[next] = 1;
					d[next] = d[now] + 1;
					v[next] = "D";
					from[next] = now;
				//	v[next] = v[now] + "D";
				}
			}

			// S, N->N+1
			if (now + 1 < MAX)
			{
				int next = now + 1;
				if (chk[next] == 0)
				{
					q.push(next);
					chk[next] = 1;
					d[next] = d[now] + 1;
					v[next] = "S";
					from[next] = now;
					//v[next] = v[now] + "S";
				}
			}

			// L, LEFT SHIFT
			if (shift(now, 1) < MAX)
			{
				int next = shift(now, 1);
				if (chk[next] == 0)
				{
					q.push(next);
					chk[next] = 1;
					d[next] = d[now] + 1;
					v[next] = "L";
					from[next] = now;
					//v[next] = v[now] + "L";
				}
			}

			// R, RIGHT SHIFT
			if (shift(now, 0) < MAX)
			{
				int next = shift(now, 0);
				if (chk[next] == 0)
				{
					q.push(next);
					chk[next] = 1;
					d[next] = d[now] + 1;
					v[next] = "R";
					from[next] = now;
					//v[next] = v[now] + "R";
					//cout << v[next];
				}
			}
		}

		// 결과 출력		
		int tt = b;
		for (int k = 0; k < d[b]; k++)
		{
			cout << v[tt];
			tt = from[tt];
		}
		cout << '\n';
		//cout << d[b] << '\n';
		//cout << v[b] << '\n';

	}


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

djm03178 6년 전 0

시간 초과 이전에 문제를 제대로 이해하지 못하신 것 같습니다.

a. 2 * now가 MAX 이상이면 2를 곱하는 걸 포기하라고 되어 있나요?

b. now + 1이 MAX 이상이면 1을 더하는 걸 포기하라고 되어 있나요?

그리고 ios_base::sync_with_stdio(false); 는 main 함수 시작에 딱 한 번만 쓰면 됩니다. 11번째 줄에는 필요하지 않습니다.

이 문제의 경우 입력과 출력이 번갈아서 이루어지기 때문에 cin.tie(NULL); 도 해주면 큰 속도 향상이 있습니다.

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

문제

문제

출처

ICPC

시간초과... 고수님들 부탁드려요

jinuu1208 6년 전 0

djm03178 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말