글 읽기 - DSLR 시간초과 나요ㅠㅠㅠ 도와주세요

jet345 5년 전 0

queue안에 vector를 저장했습니다. queue안에 들어가는 vector의 첫번째 원소는 DSLR이 적용된 string, 두번째 원소는 경로를 표현하는 string을 저장했습니다ㅠㅠ

모든 testcase에서 잘 돌아가는데 자꾸 시간초과메세지가 뜨네요 어떻게해야 안뜰까요..

#include <iostream>
#include <queue>
#include <vector>
#include <string>
using namespace std;

queue<vector<string>> q;
int isvisit[10000] = { 0, };

string zero_append(int R) { //1~999숫자가 들어왔을때 앞에 0을 붙혀주는 부분
	string result = "";
	string input = to_string(R);
	if (R >= 0 && R <= 9) {
		string a = "000";
		result = a + input;
	}
	else if (R >= 10 && R <= 99) {
		string a = "00";
		result = a + input;
	}
	else if (R >= 100 && R <= 999) {
		string a = "0";
		result = a + input;
	}
	else {
		result = input;
	}

	return result;
}

void oper_num() {
	string concat_str = "";
	string input = q.front()[0];
	string left = "";
	string right = "";
	concat_str = input + input;
	int D = stoi(input);

	int R;
	if (D * 2 > 9999) {
		R = D * 2;
		R = R % 10000;
		if (isvisit[R] == 0) {
			string a = q.front()[1] + "D";
			isvisit[R] = 1;
			q.push({ zero_append(R), a });
		}
	}
	if (D * 2 <= 9999) {
		R = D * 2;
		if (isvisit[R] == 0) {
			string a = q.front()[1] + "D";
			isvisit[R] = 1;
			q.push({ zero_append(R), a });
		}
	}
	if (D == 0) {
		R = 9999;
		if (isvisit[R] == 0) {
			string a = q.front()[1] + "S";
			isvisit[R] = 1;
			q.push({ zero_append(R), a });
		}
	}
	if (D - 1 > 0) {
		R = D - 1;
		if (isvisit[R] == 0) {
			string a = q.front()[1] + "S";
			isvisit[R] = 1;
			q.push({ zero_append(R), a });
		}
	}
	//12341234

	for (int i = 1; i < 5; i++) {
		char a = concat_str.at(i);
		left = left + a;
	}
	if (isvisit[stoi(left)] == 0) {
		string a = q.front()[1] + "L";
		q.push({ zero_append(stoi(left)),a });
		isvisit[stoi(left)] = 1;
		a = "";
	}

	for (int i = 3; i < 7; i++) {
		char a = concat_str.at(i);
		right = right + a;
	}
	if (isvisit[stoi(right)] == 0) {
		string a = q.front()[1] + "R";
		q.push({ zero_append(stoi(right)),a });
		isvisit[stoi(right)] = 1;
		a = "";
	}
}

int main() {
	int N;
	string start = "";
	string dest = "";
	string ans = "";
	string first = "";
	vector<string> answer;

	//cin >> N;
	scanf("%d", &N);
	while (N > 0) {
		cin >> start >> dest;
		start = zero_append(stoi(start));
		dest = zero_append(stoi(dest));
		q.push({ start,"" });
		isvisit[stoi(start)];

		while (1) {
			first = q.front()[0];
			if (first.compare(dest) == 0) {
				ans = q.front()[1];
				break;
			}
			oper_num();
			q.pop();
		}

		while (!q.empty()) { q.pop(); }

		answer.push_back(ans);
		start = "";
		dest = "";
		ans = "";
		first = "";
		for (int i = 0; i < 10000; i++)isvisit[i] = 0;
		N--;
	}

	for (int i = 0; i < answer.size(); i++) {
		cout << answer[i] << endl;
		//printf("%s\n", answer[i]);
	}

}

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

문제

문제

출처

ICPC

DSLR 시간초과 나요ㅠㅠㅠ 도와주세요

jet345 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말