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

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

17103번: 골드바흐 파티션

문제풀이

이 문제는 소수를 구하고, 구한 소수들끼리 더했을 때 입력받은 값이 나오는 경우의 수를 출력하는 문제이다.

일단 시간제한과 입력 사항에 "케이스의 개수 T (1 ≤ T ≤ 100)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 N은 짝수이고, 2 < N ≤ 1,000,000을 만족한다."로 인해 평범하게 소수를 구하면 시간 초과가 나는 문제이다.

 

그래서 소수는 시간복잡도가 가장 낮은 에라토스테네스의 체(아래 출처 확인)를 써야 하며 소수를 더하는 행위 또한 N번만큼 돌도록 해야 된다. 

구한 소수를 list에 담아주고 list의 왼쪽을 가르키는 left와 오른쪽의 가리키는 right 변수를 선언해준다. left와 right자리의 소수들을 더했을 때 입력받은 값보다 작다면 left를 증가시켜주고 크다면 값을 줄여주기 위해 right를 감소시켜주면 된다.

위 과정을 반복했을 때 값이 같은 구간이 나온다면 result값을 증가시켜 주고, 현재 left와 right 범위 안을 조사해야 되기 때문에 left--, right++을 해주면 된다. 그리고 left와 right가 교차될 때까지 반복하면 된다.

 

 

코드

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

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int T = Integer.parseInt(br.readLine());

		for (int i = 0; i < T; i++) {
			int num = Integer.parseInt(br.readLine());

			boolean[] isPrime = new boolean[num + 1];

			// 에라토스테네스의 체
			// 처음은 모두 소수라는 가정
			for (int j = 2; j <= num; j++) {
				isPrime[j] = true;
			}

			for (int j = 2; j * j <= num; j++) {
				if (!isPrime[j])
					continue;
				for (int k = j * j; k <= num; k += j) {
					isPrime[k] = false;
				}
			}
			
			List<Integer> list = new ArrayList<>();

			//소수만 담기
			for (int j = 2; j <= num; j++) {
				if (isPrime[j]) list.add(j);
			}
			
			int left =0;
			int right = list.size()-1;
			int result = 0;
			
			while(left<=right) {
				int a = list.get(left);
				int b = list.get(right);
				
				if(a+b > num)right--;
				else if(a+b < num) left++;
				else {
					result++;
					left++;
					right--;
				}
			}
			
			System.out.println(result);
		}
	}
}

 

출처

에라토스테네스의 체 : seokjin2.tistory.com/18