글 읽기 - 시간초과 조언좀 부탁드립니다.

ghjo92 5년 전 0

시간초과 문제입니다ㅠㅠ.

알고리즘 자체가 잘못된건지 최적화가 더 할수있는건지를 모르겠네요.

먼저 100만까지의 수중에서 소수를 골라냅니다(에라토스테네스의 체).

다음에 테스트케이스의 숫자를 입력받은 후에, 숫자에서 소수를 빼면 소수인가 아닌가로 판별을 하고 있습니다.

몇시간째 여러가지 뭔가 조작을 해봤지만 잘 안되네요 ㅠㅠ.

처음부터 구조자체가 잘못된 건지 궁금합니다. 고수님들 도움바랍니다.

#include <iostream>
//#include <vector>

using namespace std;

bool notprime[1000001]; //에라토스테네스의 체 배열
int vi[500001]; // 소수를 저장할 배열

int main()
{
	int T;
	cin >> T;
    //에라토스테네스 체
	for (int i = 2; i*i <= 1000000; i++)
	{
		if (notprime[i] == false)
		{
			for (int j = 2; i*j <= 1000000; j++)
			{
				notprime[i*j] = true;
			}
		}
	}
	//탐색할 소수저장
	int cnt = 0;
	for (int i = 2; i <= 500000; i++)
		if (notprime[i] == false)
			vi[cnt++] = i;
	
    //테스트케이스시작
	for (int ti = 1; ti <= T; ti++)
	{
		int N;
		cin >> N;
		int ans = 0;

		for (int i = 0;  i<cnt && vi[i] <= N/2; i++) // 가지고있는 소수들로 N/2까지 계산
		{
			if (notprime[N - vi[i]] == false) // N에서 소수를 빼면 소수인지 검사.
				ans++;
		}

		cout << ans << endl;
	}
	
	return 0;
}

ho94949 5년 전 1

지금은 문제 데이터가 약하지만 사실 이 문제는 너려운 사전지식을 요하는 문제입니다.

혹시 원하신다면 FFT와 convolution에 대해 찾아보시면 됩니다.

startlink 5년 전 1

이 방법으로 풀 수 있게 제한을 수정했습니다.

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

문제

문제

출처

ICPC

시간초과 조언좀 부탁드립니다.

ghjo92 5년 전 0

ho94949 5년 전 1

startlink 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말