글 읽기 - 시간초과가 자꾸 뜨는데... 고수님들 도와주세요

dudwhd93 8년 전 0

for 문이 너무 많은것 같기는 한데.. 이 코드 말고는 모르겠네요

어떻게 하면 시간을 줄일 수 있는지 도와주세요

import java.util.*;


public class Main {
	  public static void main(String[] args)  {
		  Scanner sc = new Scanner(System.in);
		  int n = sc.nextInt();
		  int[] testCase = new int[n];
		  for(int i=0; i<n; i++){
			  testCase[i] = sc.nextInt();
		  }
		  //입력 받기 끝
		  
		  for(int i=0; i<n; i++){//각 testCase 하나하나에 대해서
			  goldBach(testCase[i]);
		  }
		  
	  }
	  
	  public static void goldBach(int n){
		  int head=0,tail=0;
		  
		  for(int i=3; i<=n/2; i++){
			  for(int j=n-1; j>=n/2; j--){
				  if(isPrime(i) && isPrime(j) && (i+j)==n){
					  head = i;
					  tail = j;
				  }
			  }
		  }
		  
		  System.out.println(head+" "+tail);
	  }
	  
	  public static boolean isPrime(int n){
		  for(int i=2; i<=(n/2); i++){
			  if(n%i == 0){
				  return false;
			  }
		  }
		  return true;
	  }
		 
}

amugeona 8년 전 0

n/2 까지 보는 isPrime 함수는 사실 sqrt(n) 까지만 보면 됩니다.

kookmin20103324 8년 전 0

짝수가 2*n 이란 성질을 이용하면 i,j의 시작지점을 각각 n으로 잡고 문제를 풀면

처음 발견되는 두 수의 차이가 가장 작게 되는 점을 이용하면 시간을 더욱 줄일 수 있습니다.

flflds0811 8년 전 0

소수를 찾는 빠른 방식 (에라토스테네스의 체)와 바이너리 서치를 통해서 문제를 접근하시면 빠르게 해결할 수 있습니다.

일반적인 방식에서는 시간초과가 나기 쉽습니다.

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

문제

문제

출처

ICPC

시간초과가 자꾸 뜨는데... 고수님들 도와주세요

dudwhd93 8년 전 0

amugeona 8년 전 0

kookmin20103324 8년 전 0

flflds0811 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말