[백준-자바] 9020번 골드바흐의 추측 / 2022.02.07

 

https://www.acmicpc.net/problem/9020

9020번: 골드바흐의 추측

 

 

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
   public static boolean isPrime(int num) { // 소수인지 판별하는 함수
	      if(num==1) // 1이면 소수가 아님
	         return false;
	      if(num==2) // 2면 소수임
	         return true;
	      for(int i=2; i*i<=num; i++) { // 자기자신보다 작은 수로 나누었을때 나머지가 0이라면
	         if(num%i==0)           // 소수가 아니므로 false 리턴
	            return false;
	      }
	      return true;     // 자기자신보다 작은 수로 나누었을 때 나누어지는 수가 없다면
	                       // true 리턴
	} 
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        
        for(int i=0; i<T; i++) { // 테스트 케이스
        	ArrayList <Integer> cha = new ArrayList<>(); // 두 소수의 차를 비교하기 위해서 arraylist 선언
        	int num = sc.nextInt(); // 숫자 입력
        	int first = 2; // 두 소수 중에 첫번째 소수를 저장할 변수
        	while(true) {
        		if(isPrime(first)) { // first가 소수라면
        			int second = num-first; // 두번째 수의 값은 num-first를 한 값 
        			if(isPrime(second) && !cha.contains(first)) { // 만약 second가 소수이고, 
                    //arraylist cha에 포함이 되어있지않은 소수라면(중복방지)
        				cha.add(first);  
        				cha.add(second); // 두 개의 소수를 arraylist에 추가해줌
        			}
        		}
        		if(first == num) // first가 num과 같다면 무한루프 탈출
        			break;
        		first++; // 다음 first 
        	}

        	int sub = cha.get(1)-cha.get(0); // 첫번째 골드바흐 파티션의 차
        	int realFirst = cha.get(0);      // 출력할 첫번째 소수 변수
        	int realSecond = cha.get(1);     // 출력할 두번째 소수 변수
        	for(int j=2; j<cha.size(); j+=2) {
        		if(sub > cha.get(j+1)-cha.get(j)) { // 2 3 비교 -> 4 5 비교 -> ...
        			realFirst = cha.get(j);
        			realSecond = cha.get(j+1);
        		}
        	}
        	System.out.println(realFirst+" "+realSecond); // 두 소수의 차가 제일 적은 두 소수 출력
        		
        }       
    }
}

 

풀이 : 

num = 16 일 때, 파티션은 총 2개이다 -> 3+13 or 5+11 이 경우에는 두 수의 차가 적은 것을 출력해야 하므로 5와 11이 답이다.

 

1)

first = 2, second = 16-2 = 14

: second가 소수가 아니므로 넘어감

 

first = 3, second = 16-3 = 13

: second가 소수이므로 arraylist cha에 first, second를 add 해줌

 

first = 4 : first가 소수가 아니므로 넘어감

 

first = 5, second = 16-5 = 11

: second가 소수가 아니고 cha에 포함되어있는 수도 아니므로 (중복 방지) add 해줌

 

first가 num이 될 때 까지 위 상황을 반복

 

2) 

무한루프 가 끝나면 arraylist cha의 상태는 다음과 같다

cha.get(0) = 3

cha.get(1) = 13 // 첫 번째 파티션

cha.get(2) = 5

cha.get(3) = 11 // 두 번째 파티션

 

sub 변수를 선언하여 첫 번째 파티션의 차인  cha.get(1)-cha.get(0) 를 대입해준다

realFirst 변수에는 첫 번째 파티션의 첫 번째 소수를 realSecond 변수에는 첫 번째 파티션의 두 번째 소수를 대입해준다.

 

3)

for문을 활용하여 첫 번째 파티션의 차 (sub)와 두 번째 파티션의 차를 비교해준다 

만약, 두 번째 파티션의 차가 더 작다면 realFirst 변수에는 두 번째 파티션의 첫 번째 소수를 realSecond 변수에는 두 번째 파티션의 두 번째 소수를 대입한다.

 

4)

첫 번째 파티션의 차는 10이고 두 번째 파티션의 차는 6이므로 두 번째 파티션이 출력된다