글 읽기 - 이게 왜 맞은 거죠?

oh20020409 2년 전 0

백트래킹으로 풀어봤는데요.

아래의 예제를 제가 작성한 소스를 이용해 실행하면 매우 느리게 답이 나오는데요.

문제를 맞은 게 이상해서 질문드려요. 분명 1초 안에 푸는 문제로 되어있는데 말이죠.

9
> < < < > > > < <

#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
using namespace std;
bool visited[10];
string MIN="999999999";
string MAX = "0";
vector<char> arr;
vector<char> list;
int N;
void check_list()
{
	bool check = 0;
	for (int i = 0; i < arr.size(); i++)
	{
		if (arr[i] == '<')
		{
			if (list[i] > list[i + 1])
			{
				check = true;
				break;
			}
		}
		else
		{
			if (list[i] < list[i + 1])
			{
				check = true; 
				break;
			}
		}
	}
	if (!check)
	{
		string temp = "";
		for (int i = 0; i < list.size(); i++)
		{
			temp += list[i];
		}
		MAX = max(MAX, temp);
		MIN = min(MIN, temp);
	}
}
void dfs()
{
	if (list.size() == N+1)
	{
		check_list();
		return;
	}
	for (int i = 0; i < 10; i++)
	{
		if (!visited[i])
		{
			visited[i] = true;
			list.push_back((char)(i+'0'));
			dfs();
			list.pop_back();
			visited[i] = false;
		}
	}
}
int main()
{
	cin >> N;
	arr.resize(N);
	for (int i = 0; i < N; i++) cin >> arr[i];
	dfs();
	cout << MAX << '\n' << MIN;
}

byeongkeunahn 2년 전 1

로컬에서 디버그 모드로 실행 중인지 확인 부탁드려요.

oh20020409 2년 전 0

답변 달아주셔서 감사해요.

visual stduio 에서 디버그 하지 않고 해도 비슷한 시간이 걸리고,

dev c로 했는데 바로 답이 나오네요.

무슨 이유라도 있는 걸까요?

byeongkeunahn 2년 전 0

Visual Studio에서 "릴리즈 모드"로 실행하셨나요? 단순히 Ctrl+F5로 실행하는 것을 말하는 게 아닙니다.

oh20020409 2년 전 0

아 처음 알았습니다. 감사합니다. ㅎㅎ

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

문제

문제

출처

ICPC

이게 왜 맞은 거죠?

oh20020409 2년 전 0

byeongkeunahn 2년 전 1

oh20020409 2년 전 0

byeongkeunahn 2년 전 0

oh20020409 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말