글 읽기 - String 시간초과 질문

hhs250 4년 전 0

string을 안쓰고 배열에 넣어서 출력하면 맞는데, 다음 코드와 같이 string을 써서 파라미터로 넘기면

시간초과가 나옵니다. string이 오래 걸려서 그런건가요?

#include <stdio.h>
#include <iostream>
#include <string>
#include <string.h>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

#define INF 0x7fffffff
struct st
{
	int num;
	string s;
};
int t, n;
queue <st> q;
bool visited[1000001], flag;

void bfs()
{
	while (!q.empty())
	{
		int num = q.front().num;
		string s = q.front().s;
		q.pop();

		if (num == 0)
		{
			flag = true;
			cout << s << "\n";
			return;
		}

		if (!visited[(num * 10) % n])
		{
			visited[(num * 10) % n] = true;
			q.push({ (num * 10) % n, s + "0" });
		}
		if (!visited[(num * 10 + 1) % n])
		{
			visited[(num * 10 + 1) % n] = true;
			q.push({ (num * 10 + 1) % n, s + "1" });
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> t;

	while (t--)
	{
		cin >> n;
		visited[1] = true;
		q.push({ 1,"1" });
		bfs();

		if (flag == false)
			cout << "BRAK\n";

		flag = false;
		memset(visited, false, sizeof(visited));
		while (!q.empty())
			q.pop();
	}
	return 0;
}

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

문제

문제

출처

ICPC

String 시간초과 질문

hhs250 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말