공부 96일차: 백준 6588번 골드바흐의 추측 자바 java

6588 골드바흐의 추측

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

6588번: 골드바흐의 추측

 

 

 

---

백준 6588번 문제 골드바흐의 추측

---

문제

---

 

 

 

 

---

과정 생각해보기

---

 

https://gimbalja.tistory.com/58

몇 달 전에 비슷한 문제를 만난 적 있다

똑같은 골드바흐의 추측이라 비슷하다고 하기에도 민망하다

다른 점이라면

1) 수의 범위가 더 커졌다는 점

2) 테스트케이스가 주어지지 않는다는 점

3) 연산자까지 모두 출력해야 한다는 정도

 

 

에라토스테네스의 체를 이용하여 소수인지 아닌지 판별하고

n/2까지만(에라토스테네스의 체처럼 대칭성 이용) 반복문을 돌려 합을 확인한다

 

 

 

---

오답

---

 

악몽 수준...

이것 외에도 몇 번 더 틀렸다..

 

 

1) 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
 
public class Main {
    // 6 <= n <= 1,000,000
    public static boolean prime[] = new boolean[1_000_000];
 
    public static void main(String[] args) throws IOException{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    StringBuilder sb = new StringBuilder();
    
    int n = 0;
    
    while((n = Integer.parseInt(br.readLine())) != 0) {
        int a = 3;
        int b = n - a;
        
        getPrime();
        while(a <= n) {    //a가 n보다 커지면 안됨
            if(prime[a] == false && prime[b] == false) {
                break;
            }else {
                a += 2;    //a는 홀수
                b -= 2;
            }
        }
        if(a < n) {
            sb.append(n).append(" = ").append(a).append(" + ").append(b).append("\n");            
        }else {
            sb.append("Goldbach's conjecture is wrong.").append("\n");
        }
    }
    
    bw.write(sb.toString());
    bw.flush();
    bw.close();
    }
    
    
    // 에라토스테네스의 체
    public static void getPrime() {
        prime[0] = true;
        prime[1] = true;
        
        for(int i = 2; i <= Math.sqrt(prime.length); i++) {
            for(int j = i*i; j < prime.length; j+=i) {
                prime[j] = true;
            }
        }
    }
 
}

 

a와 b를 2씩 더하고 빼기 때문에 시간 초과가 날 거란 생각은 했지만 일단 질러봤던 코드

3부터 시작한 것 역시 꽤 무모하다고 생각했다

(근데 정답으로 인정된 코드를 보면 그게 문제가 아니다)

 

 

2)

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
 
public class Main {
    // 6 <= n <= 1,000,000
    public static boolean prime[] = new boolean[1_000_000];
 
    public static void main(String[] args) throws IOException{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    StringBuilder sb = new StringBuilder();
    
    int n = 0;
    boolean isTrue = false;    //골드바흐의 추측이 맞다면 true
    while((n = Integer.parseInt(br.readLine())) != 0) {
        getPrime();
        for(int i = 3; i <= n/2 + 1; i+=2) {
            if( !prime[i] && !prime[n-i]) {
                sb.append(n).append(" = ").append(i).append(" + ").append(n-i).append("\n");            
                isTrue = true;
                break;
            }
        }
        if(!isTrue) {
            sb.append("Goldbach's conjecture is wrong.").append("\n");            
            break;
        }
        
    }
    bw.write(sb.toString());
    bw.flush();
    bw.close();
    }
    
    
    // 에라토스테네스의 체
    public static void getPrime() {
        prime[0] = true;
        prime[1] = true;
        
        for(int i = 2; i <= Math.sqrt(prime.length); i++) {
            if(prime[i] == true) {
                continue;
            }
            for(int j = i*i; j < prime.length; j+=i) {
                prime[j] = true;
            }
        }
    }
 
}

 

여러 블로그 참고해서 수정했는데도 시간 초과가 떠서 완전 멘붕왔던 코드

 

 

 

---

정답 인정 코드

---

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
 
public class Main {
 
    public static void main(String[] args) throws IOException{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    StringBuilder sb = new StringBuilder();
    boolean[] prime = new boolean[1_000_001];
    
    //에라토스테네스의 체
    prime[0] = true;
    prime[1] = true;
    
    for(int i = 2; i <= Math.sqrt(prime.length); i++) {
        if(prime[i] == true) {
            continue;
        }
        for(int j = i*i; j < prime.length; j+=i) {
            prime[j] = true;
        }
    }
    
    int n = 0;
    boolean isTrue = false;    //골드바흐의 추측이 맞다면 true
    while((n = Integer.parseInt(br.readLine())) != 0) {    //0이 입력되면 끝
        // 홀수 소수끼리의 합 -> 첫 홀수 소수인 3부터 +2씩 / 대칭성때문에 n/2까지
        for(int i = 3; i <= n/2 + 1; i+=2) {    
            if( !prime[i] && !prime[n-i]) {    //둘다 소수라면
                sb.append(n).append(" = ").append(i).append(" + ").append(n-i).append("\n");            
                isTrue = true;    //이 수에 관한 골드바흐의 추측은 맞다
                break;
            }
        }
        if(!isTrue) {    //골드바흐의 추측이 틀렸다면
            sb.append("Goldbach's conjecture is wrong.").append("\n");            
            break;
        }
        
    }
    bw.write(sb.toString());
    bw.flush();
    bw.close();
    }
}

 

그래서 static 멤버들의 위치를 옮겼고.. 정답 인정됐다!

 

주석에 자세하게 설명을 적었다

 

 

 

---

오랜만에 만난 에라토스테네스의 체.. 거의 다 까먹었던 것 같다

 

사실 아직도 의아하다

static 변수랑 static 메서드의 위치를 옮긴 것만으로 시간 초과가 해소된 거라..

static 멤버들이 시간에도 영향을 주는 건가..? 싶다

 

시간복잡도 생각해내는 게 너무 어렵다