[백준] 6588번. 골드바흐의 추측(JAVA)

문제

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

---

풀이(25분)

import java.io.*;
import java.util.*;

public class Main {

    static List<Integer> primeLists = new ArrayList<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        dijkstra(); // 소수 리스트 파악
        StringBuilder sb = new StringBuilder(); // 정답 출력을 위한 객체 생성

        while(n != 0){
            int endIdx = binarySearch(n); // 효율적 탐색을 위한 최종 인덱스 설정
            int[] num = twoPointer(n, endIdx); // 정답 탐색
            if(num == null){ // 정답이 없다면
                sb.append("Goldbach's conjecture is wrong.\n");
                continue;
            }
            sb.append(n).append(" = ").append(num[0]).append(" + ").append(num[1]).append("\n");
            n = Integer.parseInt(br.readLine());
        }
        System.out.println(sb.toString());
    }

    static int binarySearch(int target){
        int start = 0;
        int end = primeLists.size() - 2;
        int mid = (start + end) / 2;
        while(start <= end){
            mid = (start + end) / 2;
            if(primeLists.get(mid) > target){
                end = mid - 1;
                continue;
            }
            if(primeLists.get(mid) < target){
                start = mid + 1;
            }
        }
        return mid + 1;
    }

    static int[] twoPointer(int target, int endIdx){
        int start = 1;
        int end = endIdx;
        while(start <= end){;
            int startNum = primeLists.get(start);
            int endNum = primeLists.get(end);

            if(target ==  startNum + endNum){ // 목표에 다 왔다면
                return new int[]{startNum, endNum};
            }
            if(target <  startNum + endNum){ // 원하는 값보다 작다면
                end--;
                continue;
            }
            start++;
        }
        return null;
    }

    static void dijkstra(){
        boolean[] isPrime = new boolean[1_000_001];
        Arrays.fill(isPrime, true);
        isPrime[0] = false;
        isPrime[1] = false;
        for(int i = 2; i <= Math.sqrt(1_000_001); i++){
            if(!isPrime[i]){
                continue;
            }
            for(int j = i * i; j <= 1_000_000; j += i){
                isPrime[j] = false;
            }
        }
        // 이제 소수만 리스트에 추가
        for (int i = 2; i <= 1_000_000; i++) {
            if (isPrime[i]) {
                primeLists.add(i);
            }
        }
    }
}

---

문제 풀이 전략

 

실버 1 문제치고 많은 개념이 들어갔다.

 

일단 문제에서 짝수 = 소수 + 소수로 나타낼 수 있다고 한다. 물론 홀수인 소수지만 2를 제외하면 모두 홀수이므로 그 부분은 넘어가자.

💡 그렇다면 우선되는 것은 소수를 찾아야 한다. -> 에라토스테네스의 체를 이용하자.

[도구정리] 에라토스테네스의 체

---

소수를 모두 찾았다면, 이제 어떤 두 소수의 합이 원하는 짝수를 만들어내는지 찾으면 된다.

💡 투포인터를 이용하여 원하는 인덱스와 값을 찾아낼 것이다.

만약 그렇지 못한다면 null을 반환하여 해당하는 문구를 출력해 주면 된다.

[도구정리] 투포인터

---

하지만 막무가내로 투포인터를 사용하면 100만 이하의 소수가 78000개정도인데 너무 많지 않을까?

-> 투포인터는 특성상 인덱스를 확 줄이지 않기 때문에 꽤 큰 부담이 될 수 있다.

💡 이분탐색을 통해 끝 인덱스를 효율적으로 찾아내자.

이분탐색을 통해 최종 인덱스를 찾아 그 부분에서부터 줄여나간다면 더욱 효율적인 연산이 가능할 것이다.

[도구정리] Binary Search(이분탐색/이진탐색)

---

최종적으로 모든 결과들을 통합해 답을 출력하면 된다!