글 읽기 - 시간 초과의 원인을 모르겠습니다... 어떻게 줄일 수 있을까요? ㅠ

kim031504 4년 전 0

C++의 STL의 set을 이용하면

중복 제거 / 오름차순 정렬을 합니다.

때문에 이를 이용하여

주어진 배열에 대해 1부터 N까지 택하는 조합을 모두 따져

조건을 만족할 때마다 답을 갱신하는 방식으로 처리하였지만,

시간에서 걸리네요... ㅠ

코드에 대한 자세한 설명은 주석으로 달아놨습니다.

이 부분에서 어떻게 시간을 단축시킬 수 있을까요...?

#include <iostream>
#include <set>
#include <algorithm>
#include <vector>

using namespace std;


// 결과용 set
set<int> result;


// 위와 아래 수열에 대해서 M개를 선택하는 것에 대한 컨테이너!
vector<int> upper_v, lower_v;


// 위와 아래의 배열용
int upper_arr[101];
int lower_arr[101];

int N, M;

// 조합으로 완전 탐색을 통해 조건을 만족할 때마다 갱신해 나간다.
void DFS(int count)
{
	if (upper_v.size() == M)
	{
		// vector -> set
		set<int> upper_set(upper_v.begin(), upper_v.end());
		set<int> lower_set(lower_v.begin(), lower_v.end());


		// 만일 중복이 없고, 구성 요소가 갖다면
		if (upper_set == lower_set)
		{
			// 결과 값 갱신!
			result = upper_set;
		}


		return;
	}

	for (int i = count; i <= N; i++)
	{
		if (upper_v.size() < M)
		{
			upper_v.push_back(upper_arr[i]);
			lower_v.push_back(lower_arr[i]);

			DFS(i + 1);

			// 이전 단계로 가기 위한 백트래킹!
			upper_v.pop_back();
			lower_v.pop_back();
		}
	}
}


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

	// 입력!
	cin >> N;

	for (int i = 1; i <= N; i++)
	{
		int n;
		cin >> n;

		upper_arr[i] = i;
		lower_arr[i] = n;
	}


	// 브루트 포스 시작!
	for (int i = 1; i <= N; i++)
	{
		// 1부터 N까지 선택하는 조합을 구하기 위함!
		M = i;

		// 첫 인덱스부터!
		DFS(1);
	}

	// 출력!
	set<int>::iterator iter;

	cout << result.size() << '\n';

	for (iter = result.begin(); iter != result.end(); iter++)
	{
		cout << *iter << '\n';
	}

	return 0;
}

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

문제

문제

출처

ICPC

시간 초과의 원인을 모르겠습니다... 어떻게 줄일 수 있을까요? ㅠ

kim031504 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말