글 읽기 - 문제를 해결하기는 했는데 궁금증이 있어서 질문합니다

haggie 5년 전 0

제가 벡터로 처음에 문제를 풀려고 노력했는데, 시간초과가 나서 결국에는 벡터를 안 쓰고 똑같은 알고리즘으로 벡터안의 pair<int,char>를 int배열 char배열로 분리해서 풀었습니다. 궁금한거는 벡터계산과정이 시간복잡도가 큰 편에 속하는지 알고 싶습니다.

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

using namespace std;

int main() {//DSLR
	int n;
	scanf("%d", &n);
	while (n--) {
		int start, target;
		scanf("%d %d", &start, &target);
		queue<int> q;
		vector<vector<pair<int, char>>> a(10000);
		bool cnt[10000];
		for (int i = 0; i < 10000; i++) {
			cnt[i] = false;
		}
		q.push(start);
		int x;
		cnt[start] = true;
		a[start].push_back(make_pair(0, 'X'));
		while (!q.empty()) {
			x = q.front();
			q.pop();
			if (x == target) {
				break;
			}


			int t = 2 * x;
			if (t >= 10000) {
				t %= 10000;
			}
			if (!cnt[t]) {
				a[t].push_back(make_pair(x, 'D'));
				q.push(t);
				cnt[t] = true;
			}


			t = x - 1;
			if (t < 0) {
				t = 9999;
			}
			if (!cnt[t]) {
				a[t].push_back(make_pair(x, 'S'));
				q.push(t);
				cnt[t] = true;
			}


			t = (x % 1000) * 10 + x / 1000;
			if (!cnt[t]) {
				a[t].push_back(make_pair(x, 'L'));
				q.push(t);
				cnt[t] = true;
			}


			t = (x / 10) + (x % 10) * 1000;
			if (!cnt[t]) {
				a[t].push_back(make_pair(x, 'R'));
				q.push(t);
				cnt[t] = true;
			}
		}

		int p;
		char c = 'O';
		vector<char> o;
		while (1) {
			p = a[x].at(0).first;
			c = a[x].at(0).second;
			if (c == 'X') {
				break;
			}
			o.push_back(c);
			x = p;
		}
		for (int i = (int)o.size()-1; i >=0; i--) {
			printf("%c", o.at(i));
		}

		puts("");
	}
	return 0;
}

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

문제

문제

출처

ICPC

문제를 해결하기는 했는데 궁금증이 있어서 질문합니다

haggie 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말