글 읽기 - 시간초과 어떻게 해결할 수 있을까요?

jms020820 2년 전 0

같은 방식으로 6588번 해결했는데

이거는 시간초과가 뜨네요

어떻게 하면 될까요

#include <stdio.h>
#include <stdlib.h>

void f(int n[]){
    int k=0;
	int *a=(int*)calloc(1000001,sizeof(int));
	for(int q=2;q*q<=1000000;q++){
		if(a[q]==0){
			for(int w=q*q;w<=1000000;w+=q){
				a[w]=1;
			}
		}
	}

	for(int e=2;e<=1000000;e++){
		if(a[e]==0){
			n[k]=e;
			k++;
		}
	}
	free(a);
}

int main(void) {
  int *a=(int*)calloc(78499,sizeof(int));
	
	f(a);
	int n;
	scanf("%d",&n);
	
	
	for(int q=0;q<n;q++){
		int m,r=0,k=0;
		scanf("%d",&m);
		
	while(1){
			if(a[r]==999983){break;}
			if(a[r]<m&&a[r+1]>m){break;}
			r++;
		}
		
		for(int w=0;a[w]<=m/2;w++){
			for(int e=r;a[e]>=m/2;e--){
				if(a[w]+a[e]==m){
					k++;
					
				}
			}
			
			} printf("%d\n",k);
	}
	
		
	
	free(a);
  return 0;
}

bamgoesn 2년 전 1

이 코드는 6588번에선 골드바흐 파티션을 하나만 찾으면 됐기 때문에 문제가 없었지만, 이 문제에선 모든 골드바흐 파티션을 찾아야 하기 때문에 문제가 됩니다.

43행에서, w를 하나씩 올릴 때마다 매번 e를 r부터 시작해서 a[w]+a[e]인 e를 찾습니다. 그래서 m이 크면 각 w에 대해 확인해보는 e의 개수가 너무 많습니다. (대략 찾아봐야 하는 범위의 소수의 개수 제곱 정도) 그래서 6588번에서는 괜찮았지만 이 문제에선 시간초과를 받게 됩니다.

jms020820 2년 전 0

방식을 바꿨는데도 시간초과네요 ㅠㅜ

다른 방식이 있을까요(힌트라도..ㅜ)

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

void f(int n[]){
    int k=0;
	int *a=(int*)calloc(1000001,sizeof(int));
	for(int q=2;q*q<=1000000;q++){
		if(a[q]==0){
			for(int w=q*q;w<=1000000;w+=q){
				a[w]=1;
			}
		}
	}

	for(int e=2;e<=1000000;e++){
		if(a[e]==0){
			n[k]=e;
			k++;
		}
	}
	free(a);
}

bool g(int n){
	for(int q=2;q*q<=n;q++){
		if(n%q==0){ return false;}
	}
	return true;
}



int main(void) {
  int *a=(int*)calloc(78499,sizeof(int));
	
	f(a);
	int n;
	scanf("%d",&n);
	
	for(int q=0;q<n;q++){
		int m,k=0;
		scanf("%d",&m);
		
		
		for(int w=0;a[w]<=m/2;w++){
			if(g(m-a[w])){

				k++;
			}
			
			
			} printf("%d\n",k);
	}
	
		
	
	free(a);
  return 0;
}

bamgoesn 2년 전 0

m-a[w]가 소수인지 판정하는 거로 노선을 튼 건 좋지만, 그걸 해주는 g함수가 과연 충분히 효율적일까요?

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

문제

문제

출처

ICPC

시간초과 어떻게 해결할 수 있을까요?

jms020820 2년 전 0

bamgoesn 2년 전 1

jms020820 2년 전 0

bamgoesn 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말