글 읽기 - 시간초과를 어떻게 줄일 수 있을까요?

zas777 4년 전 0

처음에 제출시 계속 prime을 구하도록 구현했다가 지금은

prime은 한번만 구하는 상태입니다.

#include <iostream>
#include <vector>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;

int cnt;
int prime[10001];
vector<pair<int,int>> sum;

int main(void){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin>>t;
	for(int i=0;i<t;i++){
		int n;
		cin>>n;
		int last=0;
		int f=0;
		if(f==0){
			for(int j=2;j<=n;j++){
				bool isPrime=true;
				for(int k=2;k*k<=j;k++){
					if(j%k==0){
						isPrime=false;
						break;
					}
				}
				if(isPrime){
					prime[j]=j;
				}
			}
		}
		f++;
		for(int p=2;p<=n;p++){
			for(int u=p;u<=n;u++){
				if(prime[p]+prime[u]==n){
					sum.push_back(make_pair(prime[p],prime[u]));
				}
			}
		}
		int minVal=987654321;
		int minidx=0;
		for(int s=0;s<sum.size();s++){
			if(minVal>sum[s].second-sum[s].first){
				minVal=sum[s].second-sum[s].first;
				minidx=s;
			}
		}
		cout<<sum[minidx].first<<' '<<sum[minidx].second<<'\n';
		sum.clear();
	}
	return 0;
}

djm03178 4년 전 0

https://www.acmicpc.net/board/...

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

문제

문제

출처

ICPC

시간초과를 어떻게 줄일 수 있을까요?

zas777 4년 전 0

djm03178 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말