글 읽기 - 시간초과 질문입니다.

car584 1년 전 0

소수를 구하는부분에서는 시간초과가 아닌것같은데 뒤의연산부분에서 시간초과가 나는것이겠죠? 다른방법이 또 있을까 궁금합니다.

#include <cstdio>

#define L 5100

int main() {
	int t;
	int arr[L];
	arr[0] = arr[1] = 0;
	for (int i = 2; i < L; i++) arr[i] = i;
	for (int i = 2; i < L; i++) { //에라토스테네스의 체를 통해 소수 찾기(5100까지)
		if (arr[i] == 0) continue;
		for (int j = i + i; j < L; j += i) arr[j] = 0;
	}


	scanf("%d", &t);

	for (int i = 0; i < t; i++) {
		int n;
		scanf("%d", &n);
		for (int j = 2; j < n/2+100; j++) { //이 반복문의 시간복잡도로 인해 시간초과가 나는걸로 추청 = > 해결방법은?
			for (int k = 2; k < n/2+100; k++) { 
				if (arr[j] + arr[k] == n && arr[j] >= arr[k]) { //앞소수가 뒤소수보다 커졌을때 가장 차이가 적으므로 순서만 바꿔출력
					printf("%d %d\n", arr[k], arr[j]);
					j = n+100;
					break;
				}
			}
		}
	}
}

logicdrive 1년 전 2

21~22번째 줄을 보시면, n/2까지 가능한 소수를 전부 순환하고 있습니다.

이부분을 다음과 같은 사실을 고려하여 시간을 단축시킬 수 있습니다.

1. n에 대한 두 소수의 합을 구하는 문제이기 때문에, 하나의 수를 구했을 경우, 나머지 수는 자연스럽게 n-(구해진수)로 고정시킬 수 있습니다. => O(n^2) > O(n)으로 시간복잡도 감소

2. 두 소수의 합이기 때문에 소수인 것만 따로 리스트에 저장해서 순환시킬 수 있습니다. => O(n) => O(n이하의 소수의 개수)로 시간복잡도 감소

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

문제

문제

출처

ICPC

시간초과 질문입니다.

car584 1년 전 0

logicdrive 1년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말