글 읽기 - 집합을 이용해 풀었지만 시간초과 ㅠㅠ

kim031504 4년 전 0

집합의 성질 중

중복 제거
자동 오름차순 정렬

이 있습니다.

완전 탐색 기법과 함께 이를 이용하여 문제에 접근을 하였는데,

시간초과가 나네요 ㅠㅠ

좀 더 줄일 수 있는 방법이 있을까요?

코드의 자세한 설명은 주석으로 달아놨습니다!

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

using namespace std;

int K, N, M;

int arr[101];

vector<int> vc;

set<int> s;


// 모든 경우의 수를 찾아 다닐 것이다. i는 행이라 생각하자.
void brute_force(int i)
{
	// M번째 행까지의 탐색이 끝났다면
	if (i == M)
	{
		int result = 1;

		// 소수의 곱을
		for (auto i : vc)
		{
			result *= i;
		}

		// 집합에 집어넣는다. 자동으로 오름차순 정렬을 하면서 중복을 제거한다.
		s.insert(result);
	}
	else
	{
		// 각 행의 모든 열을 돈다.
		for (int j = 0; j < K; j++)
		{
			// 각각 열에 대해서 값을 담는다.
			vc.push_back(arr[j]);

			// 다음 행으로 넘어간다.
			brute_force(i + 1);

			// 되돌리기!
			vc.pop_back();
		}
	}
}

int main()
{

	/*
		입력!
	*/
	scanf("%d %d", &K, &N);

	for (int i = 0; i < K; i++)
	{
		scanf("%d", &arr[i]);
	}


	/*
		완전 탐색 시작!
	*/
	for (int i = 1; i <= K; i++)
	{
		M = i;

		brute_force(0);
	}

	int cnt = 1;

	// N 번째에 다다르면 출력 후 종료!
	for (set<int>::iterator it = s.begin(); it != s.end(); it++)
	{
		if (cnt == N)
		{
			printf("%d\n", *it);
			break;
		}

		cnt++;
	}

	
	return 0;
}

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

문제

문제

출처

ICPC

집합을 이용해 풀었지만 시간초과 ㅠㅠ

kim031504 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말