[BOJ - JAVA] 6588 - 골드바흐의 추측

# 주소

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

6588번: 골드바흐의 추측

 

# 문제

 

# 문제 해설 및 코드 리뷰

 

import java.util.Scanner;
public class Main{
	public static final int Max = 1000000;
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        boolean[] dp = new boolean[Max + 1];
        
        for(int i = 2; i <= Max; i++) {
        	dp[i] = true;
        }
        for(int i = 2; i <= Max; i++) {
        	for(int j = i * 2; j<= Max; j+=i) {
        		if(!dp[j])
        			continue;
        		dp[j] = false;
        	}
        }
        while(true) {
        	int n = scan.nextInt();
        	boolean ok = false;
        	if(n == 0)
        		break;
        	for(int i = 2; i <= n/2; i++) {
        		if(dp[i] && dp[n-i]) {
        			System.out.println(n + " = " + i + " + " + (n-i));
        			ok = true;
        			break;
        		}
        	}
        	if(!ok)
        		System.out.println("Goldbach's conjecture is wrong.");
        }
    }
}

배열 범위가 1000000까지 인거 보고 자칫하다간 시간초과 날거같아서 정석대로 풀어야 했습니다.

이 문제를 풀기 전에 아리스토테네스의 체 개념을 숙지하셔야 하는데, 관련 자료는 

https://terms.naver.com/entry.naver?docId=1179083&cid=40942&categoryId=32204 

에라토스테네스의 체

여기에서 확인하시면 되겠습니다.

 

boolean 타입의 dp배열을 먼저 생성합니다.

이후 dp의 모든 값을 true로 바꾸어 주고 이중 for문을 이용해, dp 배열에서 i가 2의 배수일 때(2를 제외하고), 3의 배수일 때(3을 제외하고) dp값을 false로 바꾸어 줍니다. 

이런식으로 모든 소수의 인덱스를 false로 바꿉니다.

이제 while문으로 들어가 n이 0일 때 입력을 종료한다고 하였으므로 n == 0 일 땐 break;

 

boolean 타입의 ok를 false로 먼저 선언하고 다시 for문을 짭니다.

이 문제의 출력 조건을 맞추기 위해 "20 = 3 + 17" 형태로 출력되게끔 짜려면

앞에 나오는 3을 나타내는 부분이 뒤의 17보다 커지면 안됩니다.

즉, 먼저 나오는 value값은 20의 절반인 10보다 작거나 같아야 합니다.

따라서 for문을 n/2까지만 범위를 생각하고 문제를 풀면 되겠습니다.

이후 dp[i]와 dp[n-i] ( 앞의 value와 뒤의 value가 모두 소수이면 참이므로)가 참일 때

Sys.out.문으로 출력하면 되겠습니다.

 

문제 출력 조건에서 n = a + b일 때 b - a가 최대가 되는 것을 원칙으로 하였으므로 a를 가장 작은 수, b를 가장 큰 수로 두는 것이 목표입니다. 따라서 a를 작은 값 부터 체킹하여 a와 b모두 소수인지를 판단하면 되겠습니다.

다시 본론으로 돌아가, Sys.out으로 식을 표현한 후 ok 를 true로 변경하고 for문을 빠져나옵니다.

계속해서 n값을 입력 받으면서 0이 입력될 때 까지 while문은 가동됩니다.

그리고 소수인 값이 없을 경우, 즉 ok가 false일 경우엔 문제에서 나왔듯이

Goldbach's conjecture is wrong.를 출력하면 되겠습니다.

감사합니다.