[백준] 9020번 : 골드바흐의 추측 - JAVA [자바]

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

9020번: 골드바흐의 추측

 

---

• 문제

 

 

 

소수를 이용한 문제다.

문제는 그리 어렵지 않으니 한 번 보면 금방 이해될 것이다.

 

 

 

 

※ 주의할 점

1. 2보다 큰 짝수가 주어질 때 소수의 합을 구해야 한다.
2. 소수의 합이 여러개일 경우 두 소수의 차이가 작은 것을 출력한다.
3. 두 개의 소수를 출력할 때 작은 소수부터 출력한다.

 

---

• 알고리즘 [풀이방법]

 

 

어려운 문제는 아니다.

 

먼저 소수를 boolean 배열 index로 활용하여 true 일 경우 소수가 아니고, false 일 경우 소수로 표현할 것이다.

위 소수의 정보를 담고있는 배열을 생성하기 위해 에라토스테네스의 체를 사용 할 것이다.

 

자세한 알고리즘은 아래 소수 구하는 알고리즘 포스팅을 참고하면 된다.

 

https://st-lab.tistory.com/81?category=830901

JAVA [자바] - 소수 구하는 알고리즘 및 구현

 

 

 

간단하게 알고리즘만 보고싶다면 아래 더보기를 통해 참고하길 바란다.

 

[에라토스테네스의 체 알고리즘]

 

public class Prime_3 {
 
    public static boolean[] prime;	// 소수를 체크할 배열
	public static void main(String[] args) {
 
		Scanner in = new Scanner(System.in);
        
		int N = in.nextInt();
		
		make_prime(N);
 
		for(int i = 0; i < prime.length; i++) {
			if(prime[i] == false) {	// 소수(false)일 경우 출력
				System.out.println(i);
			}
		}
	}
 
	// N 이하 소수 생성 메소드 
	public static void make_prime(int N) {
		
		prime = new boolean[N + 1];	// 0 ~ N
 
		/*
		소수가 아닌 index = true
		소수인 index = false
		*/

        
		prime[0] = prime[1] = true;
		
        
		// 제곱근 함수 : Math.sqrt()
		for(int i = 2; i <= Math.sqrt(number); i++) {
        
			// 이미 체크된 배열이면 다음 반복문으로 skip
			if(prime[i]==true) {
				continue;
			}
        
			// i 의 배수들을 걸러주기 위한 반복문
			for(int j = i*i; j < prime.length; j = j+i) {
				prime[j] = true;
			}
		}
 
	}
 
}

 

 

 

 

 

 

---

 

그럼 본격적으로 알고리즘 접근방법을 설명하겠다.

 

골드바흐의 추측은 정수론의 미해결 문제 중 가장 유명한 문제가 아닐까 싶다.

"2보다 큰 모든 짝수는 2개의 소수의 합으로 표현 할 수 있다."

 

물론 미해결 문제라고 해서 풀지 못하는 것은 아니다.

대부분 '참'일 것이라고 판단한다. 다만 증명하진 못했을 뿐..

 

일단 10¹⁸ 까지는 증명이 되었으니 10000 이하의 짝수는 참일 것이다.

 

 

그리고 간략하게 알고리즘만 설명 할 것이라 의사코드로 표현하겠다.

 

 

 

 

 

 

 

1 단계 : 소수를 index 로 표현한 배열 만들기

 

 

소수를 구하는 알고리즘은 앞서 링크를 통해 참고하라고 했으니 별다른 설명은 안할 것이다.

 

문제에서 나와있는대로 0 ~ 10000 까지의 배열을 생성하고

에라토스테네스의 체를 이용하여 소수를 구할 것이다.

 

class Main {
	/*
		소수 아님 = true
		소수 = false
	*/
	boolean[] prime = new boolean[10001];
    
 
	main() {
		get_prime();
	}
    
    
	// 소수 알고리즘
	void get_prime() {
    
		prime[0] = prime[1] = true;

		for (int i = 2; i <= Math.sqrt(prime.length); i++) {
			if (prime[i]) continue;
            
			for (int j = i * i; j < prime.length; j += i) {
				prime[j] = true;
			}
		}
	}

}

 

 

 

 

 

 

 

 

 

2 단계 : 테스트 케이스 T를 입력받아 반복문을 만들고 짝수 n 을 입력받기

 

 

먼저 테스트케이스 T를 입력받아 while문으로 반복문을 만든다.

그리고 반복문 안에서 n 을 입력받는다.

 

class Main {
	/*
		소수 아님 = true
		소수 = false
	*/
	boolean[] prime = new boolean[10001];
    
 
	main() {
		get_prime();

		int T = input();	// 테스트케이스

		while(T-- > 0) {
			int n = input();
		}
	}
    
    
	/*
	소수 알고리즘 생략
	*/

}

 

 

 

 

 

 

 

 

 

 

 

 

3 단계 : 짝수 n 에 대하여 두 소수 구하기

 

 

여기서 중요한 포인트는 만약 정답이 여러개일 경우 두 소수의 차가 작은 것을 출력하라고 했다.

 

예로들어 짝수 14 에 대하여 두 소수의 합이 14 인 소수는 아래와 같다.

7 + 7 = 14

3 + 11 = 14

 

이렇게 두 케이스가 존재할 때 두 소수의 차가 작은, 즉 7 7 을 출력하라는 것이다.

 

그러면 위 조건을 만족하면서 두 소수를 구하는 방법을 찾아야한다.

어떻게 해야할까?

 

매우 간단하다.

짝수 n 을 절반을 나누어서 검사하면 된다.

 

무슨말인가 하면

 

n = p + q ( p 와 q는 소수 ) 일 때,

예로들어 n = 16 이 주어진다고 해보자.

그럼 일단 p 와 q 에 16을 절반으로 나눈 8 을 각각 저장한다고 생각하자.

 

그리고 p 와 q 가 소수가 아니라면 p 는 1 감소, q 는 1 증가시키면서 p 와 q 가 소수일 때 까지 찾는 것이다.

 

표로 그리면 아래와 같을 것이다.

 

p	q	n = p + q	True/False
8	8	16	False
7	9	16	False
6	10	16	False
5	11	16	True
4	12	16	False
3	13	16	True
2	14	16	False

 

 

즉 8, 8 부터 시작하여 5, 11 일때 두 수가 모두 소수이니 반복문을 종료하고 해당 수를 출력하면 되는 것이다.

이를 토대로 알고리즘을 짜면 아래와 같다.

 

class Main {
	/*
		소수 아님 = true
		소수 = false
	*/
	boolean[] prime = new boolean[10001];
    
 
	main() {
		get_prime();

		int T = input();	// 테스트케이스

		while(T-- > 0) {
			int n = input();
			int p = n / 2;
			int q = n / 2;

			while(true) {
				if(prime[p]==false && prime[q]==false) {
					print(p + " " + q + "\n");
					break;
				}
				p--;
				q++;
			}
		}
	}
    
    
	/*
	소수 알고리즘 생략
	*/

}

 

 

 

위와같이 알고리즘을 짜면 된다.

 

 

 

 

 

---

• 3가지 방법을 이용하여 풀이한다.

 

알고리즘은 크게 다를 것이 없다.

다만 입출력 방법의 차이에 따른 성능을 보여주고자 한다.

 

입력은 Scanner 와 BufferedReader 을 통한 방법으로 보여줄 것이고,

출력은 일반적인 출력방법과 StringBuilder 을 사용한 방법을 보여주려 한다.

 

---

• 풀이

- 방법 1 

import java.util.Scanner;

public class Main {

	/*
		false : 소수
		range : 0 ~ 10000
	*/
	public static boolean[] prime = new boolean[10001];

	public static void main(String[] args) {

		Scanner in = new Scanner(System.in);
		
		get_prime();

		int T = in.nextInt();	// 테스트케이스

		while (T-- > 0) {
			int n = in.nextInt();
			int first_partition = n / 2;
			int second_partition = n / 2;

			while (true) {
            
				// 두 파티션이 모두 소수일 경우
				if (!prime[first_partition] && !prime[second_partition]) {
					System.out.println(first_partition + " " + second_partition);
					break;
				}
				first_partition--;
				second_partition++;
			}
		}

	}

	// 에라토스테네스의 체
	public static void get_prime() {
		prime[0] = prime[1] = true;

		for (int i = 2; i <= Math.sqrt(prime.length); i++) {
			if (prime[i])
				continue;
			for (int j = i * i; j < prime.length; j += i) {
				prime[j] = true;
			}
		}
	}

}

 

 

위 알고리즘 설명에서 설명했던 방법을 그대로 차용해서 짠 코드다.

어렵지 않게 짤 수 있을 것이다.

 

참고로 소수인 경우가 false 이므로 이 점 혼돈하지 않으시길 바란다.

 

---

- 방법 2 

 

입력방법을 Scanner 에서 BufferedReader 로 변경하여 푼 방법이다.

알고리즘은 같다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {

	/*
		false : 소수
		range : 0 ~ 10000
	*/
	public static boolean[] prime = new boolean[10001];

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		get_prime();

		int T = Integer.parseInt(br.readLine());	// 테스트케이스

		while (T-- > 0) {
			int n = Integer.parseInt(br.readLine());
			int first_partition = n / 2;
			int second_partition = n / 2;

			while (true) {
            
				// 두 파티션이 모두 소수일 경우
				if (!prime[first_partition] && !prime[second_partition]) {
					System.out.println(first_partition + " " + second_partition);
					break;
				}
				first_partition--;
				second_partition++;
			}
		}

	}

	// 에라토스테네스의 체
	public static void get_prime() {
		prime[0] = prime[1] = true;

		for (int i = 2; i <= Math.sqrt(prime.length); i++) {
			if (prime[i])
				continue;
			for (int j = i * i; j < prime.length; j += i) {
				prime[j] = true;
			}
		}
	}

}

 

 

입력방법만 바뀌었으니 그리 어려울 건 없을 것이다.

---

- 방법 3 

 

 

필자가 출력할 케이스들이 많을 때 가장 많이 사용하는 방법 중 하나다.

StringBuilder 로 출력 할 문자열을 하나로 묶어서 마지막에 한 번에 출력하는 방법이다.

 

출력량이 많아지면 많아질수록 좋은 성능을 보인다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {

	/*
		false : 소수
		range : 0 ~ 10000
	*/
	public static boolean[] prime = new boolean[10001];

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		get_prime();

		int T = Integer.parseInt(br.readLine());	// 테스트케이스

		while (T-- > 0) {
			int n = Integer.parseInt(br.readLine());
			int first_partition = n / 2;
			int second_partition = n / 2;

			while (true) {
            
				// 두 파티션이 모두 소수일 경우
				if (!prime[first_partition] && !prime[second_partition]) {
					sb.append(first_partition).append(' ').append(second_partition).append('\n');
					break;
				}
				first_partition--;
				second_partition++;
			}
		}
		System.out.print(sb);
	}

	// 에라토스테네스의 체
	public static void get_prime() {
		prime[0] = prime[1] = true;

		for (int i = 2; i <= Math.sqrt(prime.length); i++) {
			if (prime[i])
				continue;
			for (int j = i * i; j < prime.length; j += i) {
				prime[j] = true;
			}
		}
	}

}

 

 

아무래도 출력 메소드 (System.out.println()) 을 반복적으로 써주면 스트림으로 반복적으로 문자를 보내다보니 성능이 저하된다.

 

이를 방지하기 위해 하나의 문자열로 이어서 한 번에 보내면 성능이 좋아진다.

자세한 성능차이는 아래에서 확인해보자.

 

 

 

 

 

 

 

---

• 성능

 

위에서 부터 순서대로

 

채점 번호 : 19610229  -  방법 3 : BufferedReader + StringBuilder

채점 번호 : 19610223  -  방법 2 : BufferedReader

채점 번호 : 19610221  -  방법 1 : Scanner

 

 

보다시피 입력과 출력 방식에 따라 성능이 꽤 차이난다는 것을 볼 수 있다.

특히나 입력의 경우 BufferedReader 와 Scanner 의 성능차이는 많이 차이난다.

---

• 정리

 

소수를 이용하는 문제라 소수를 구하는 방법만 알면 매우 쉽게 접근할 수 있는 문제였다.

그리 어려운 문제는 아니니 보다 중점적으로 살펴볼 것은 소수를 어떻게 구해야 좀 더 빠르게 구할 수 있는지 다양한 방법을 고민해보는 것이 중요하지 않을까 싶다.