백준 #9020 java 2023.01.30

골드바흐의 추측 문제..! 백준을 풀면서 한 번도 들어보지 못했던 ~~의 정리, ~~의 추측 등 새로운 수학의 법칙(?)들을 많이 접하는 것 같다.

 

package boj_basic.step8;

import java.util.Scanner;

public class Q9020 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int T = sc.nextInt();
		
		
		for(int i = 0; i<T; i++) {
			int n = sc.nextInt();
			int[] arr = new int[n+1];
			arr[1]=1;
			for(int j = 2; j<n; j++) {
				if((int)Math.pow(j, 2)>n)
					break;
				else {
					for(int k = (int)Math.pow(j, 2); k<n; k+=j)
						arr[k]=1;
				}
					
			}
			int min = n;
			String[] brr = new String[n+1];
			
			for(int j = 1; j<n+1; j++) {
				for(int k = 1; k<n+1; k++) {
					if(arr[j]==0 && arr[k]==0) {
						if(j+k==n) {
							if(j<=k) 
								brr[k-j]=Integer.toString(j)+" "+Integer.toString(k);
						}
					}
				}
			}
			for(int j = 0; j<n+1; j++) {
				if(brr[j]!=null) {
					if(j<min)
						min = j;
				}
			}
			System.out.println(brr[min]);
		}

	}

}

골드바흐 파티션이 여러가지인 경우에는 두 수의 차가 가장 작은 수를 출력하게 하도록 코드를 짜는 게 상당히 어렵고 오랜 시간이 걸렸다.

그래서 정말 많은 시간을 투자해 열심히 풀었는데..... 그런데.... 이클립스에선 실행이 아주 잘되는데...

시간초과 문제가 생겼다 ㅠㅠㅠㅠ 아무리 잘 풀어도 시간초과면 땡이기 때문에.... 너무 아쉬웠다..

근데 내가 생각해도 위 코드는 너무 반복문이 많고 시간이 오래걸리는 코드이긴 하다..^^

 

그래서 구글링을 하다가 시간을 줄일 수 있는 방법을 찾게 되었는데

package boj_basic.step8;

import java.util.Scanner;

public class Q9020_1 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int T = sc.nextInt();
		
		
		for(int i = 0; i<T; i++) {
			int n = sc.nextInt();
			int[] arr = new int[n+1];
			arr[1]=1;
			for(int j = 2; j<n; j++) {
				if((int)Math.pow(j, 2)>n)
					break;
				else {
					for(int k = (int)Math.pow(j, 2); k<n; k+=j)
						arr[k]=1;
				}
					
			}
			int num = n/2;
			int num2 = n/2;
			
			while(true) {
				if(arr[num]==0 && arr[num2]==0) {
					System.out.println(num+" " + num2);
					break;
				}
				else
					num--; num2++;
			}
		}

	}

}

num과 num2를 일단 2로 나눠주고 시작한다. (입력한 짝수 값이 8이라면 4,4)로

그리고 소수가 아니면 num은 1씩 줄어들고 num2는 1씩 커지게 해주면 된다... 진짜 천재분들....

평소에도 시간이 적게 걸리는 코드를 구현할 수 있도록 노력해야겠다.!

 

속이 뻥 뚫리는 다섯글자 "맞았습니다"^^