글 읽기 - [시간 초과]에라토스테네스의 체 응용, 도움 및 조언 주시면 감사하겠습니다!

sonejw0106 1년 전 0

11%에서 시간초과가 뜨는 것으로 보아 알고리즘이 걸리는 시간복잡도 상 문제가 있다는 것만 짐작했습니다.

알고리즘 순서는 다음과 같이 구성했습니다.

1. M, N 입력 받은 후 N+1 크기의 정수 배열 생성(0~N까지 집어넣기 위해)

2. 정수 변수 i를 인덱스로 하여 2부터 N까지 반복

2-1. i가 M보다 크거나 같으며 -1(소수가 아닌 수는 -1로 덮었습니다.)이 아닌 경우에 출력

2-2. i에 대해 i * 2 ~ i * 무언가(<= N) 를 -1로 덮었습니다.

아마 1부터 N까지 모든 소수를 구하는 것과, 반복문안에 반복문 때문에 n제곱 시간이 걸리는 것 같은데 사실 이부분도 확실하진 않습니다.

조언 주시면 감사하겠습니다!

#include <iostream>
using namespace std;

int main()
{
	int M, N;
	cin >> M >> N;
	int numbers[N + 1];// 0 ~ N
	
	for (int i = 2 ; i < N + 1 ; i ++) {
		if ((i >= M) && (numbers[i] != -1)) {
			cout << i << endl;// prime
		}
		for (int n = 2 ; n * i < N + 1 ; n ++) {
			if (numbers[i * n] != -1) {
				numbers[i * n] = -1;
			}
		}
	}
	return 0;
}

0000000000 1년 전 2

이 코드는 말씀하신 대로 O(N²)의 시간복잡도를 가집니다. 굳이 응용하기보다는 처음에 1~N 범위에 에라토스테네스의 체를 해 두시고 이후에 M~N 범위 탐색을 하시는 게 나을 겁니다. 그나저나 endl은 출력할 때마다 buffer를 flush하기 때문에 매우 느립니다. '\n'을 쓰세요.

여담으로 사실 이 문제는 그냥 O(N*sqrt(N))의 시간복잡도를 가지는 Naive 코드로도 통과가 가능합니다.

sonejw0106 1년 전 0

혹시나 해서 endl 만 \n으로 변환해서 제출해보았습니다.

전에는 11%에서 정지하더니 저거 하나 바꿨다고 통과가 되네요...

다른 시간복잡도 풀이도 한 번 살펴보아야겠습니다.

답변 감사합니다!

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

문제

문제

출처

ICPC

[시간 초과]에라토스테네스의 체 응용, 도움 및 조언 주시면 감사하겠습니다!

sonejw0106 1년 전 0

0000000000 1년 전 2

sonejw0106 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말