[백준, 자바, 17103번] 골드바흐 파티션

풀이

• 해당 문제는 짝수의 입력값이 주어졌을 때,
• 두 소수의 합이 입력값이 되는 경우를 카운팅 하는 문제로
• 기존 소수를 구한 것처럼, 에라토스테네스의 체를 활용하여
• 소수를 모두 배열에 넣은 다음
• 2중 for문으로 찾으면서, 합이 큰 경우에 대한 조건 분기를 통해
• 시간 효율을 줄이고자 했지만, 계속해서 시간 초과...
• 그래서 어떤 힌트가 있을지 찾아보니,
• (인풋값 - 소수) 의 결과값이 소수인가(bool)?를 확인 이라는 문장을 보고
• 허거덩하고 생각한 건, 찾은 소수를 Set에 넣고 좀 더 빠르게 확인하는 방법이 떠올라서
• 아래와 같이 해결할 수 있었음.
• 실패한 코드도 아래에 작성.

  

// 성공

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

public class _17103 {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int T = sc.nextInt();
        int[] li = new int[T];
        int mx = 0;
        for (int i=0; i<T; i++) {
            int n = sc.nextInt();
            if (n>mx) mx = n;
            li[i]=n;
        }

        boolean[] check = new boolean[mx+1];
        check[1]=true;
        List<Integer> prime = new ArrayList<>();

        for (int i=2; i<mx; i++) {
            if (!check[i]) prime.add(i);
            for (int j=i*2; j<=mx; j+=i) {
                if (!check[j]) check[j]=true;
            }
        }
        Set<Integer> s_li = new HashSet<>(prime);
        for (int num: li) {
            int cnt = 0;
            for (int sosu: prime) {
                if (num-sosu<sosu) break;
                else if (s_li.contains(num-sosu)) cnt++;
            }
            bw.write(cnt+"\n");
        }
        bw.flush();
    }
}

 

// 시간 초과

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

public class Main {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int T = sc.nextInt();
        int[] li = new int[T];
        int mx = 0;
        for (int i=0; i<T; i++) {
            int n = sc.nextInt();
            if (n>mx) mx = n;
            li[i]=n;
        }

        boolean[] check = new boolean[mx+1];
        check[1]=true;
        List<Integer> prime = new ArrayList<>();
        for (int i=2; i<mx; i++) {
            if (!check[i]) prime.add(i);
            for (int j=i*2; j<=mx; j+=i) {
                if (!check[j]) check[j]=true;
            }
        }
        for (int val: li) {
            int cnt = 0;
            for (int i=0; i<prime.size(); i++) {
                if (prime.get(i)>=val) break;
                for (int j=i; j<prime.size(); j++) {
                    if (prime.get(i)+prime.get(j)==val) {
                        cnt++;
                        break;
                    }
                    else if (prime.get(i)+prime.get(j)>val) break;
                }
            }
            bw.write(cnt+"\n");
        }
        bw.flush();
    }
}