• 문제: https://www.acmicpc.net/problem/6588

설명

이번 문제는 시간 초과를 잘 해결하는 것이 필요했다.

첫번째 시도: 이중 반복문 사용하기

for (int i = 0; i < primes.size(); i++) {
	for (int j = i; j < primes.size(); j++) {
    	int total = n - primes.get(i);
        total -= primes.get(j);
        if (total < 0) {
        	break;
        }
        else if (total == 0) {
        	sb.append(n).
               append(" = ").
               append(primes.get(i)).
               append(" + ").
               append(primes.get(j)).
               append("\n");
            return;
    	}
	}
}
sb.append("Goldbach's conjecture is wrong.");

이중 반복문을 사용하여 i + j == n 형태(ex. 8 = 3 + 5)로 합을 구했다. 이 경우 시간초과로 틀리게 된다.

두번째 시도: StringBuilder를 사용한다.
역시 시간초과가 발생했다.

올바른 풀이 방법: for문을 한개 써서 해결한다.

• 소수 배열과 소수인지 아닌지를 담는 boolean 배열을 만든다.
• b[n-소수]가 true이면 정답으로 보고 출력하는 형태로 만든다.
  • b[8-3] = b[5]
  • b[5] = ture => 소수이다. 3과 5 모두 소수이기 때문에 정답이 된다.

코드

package Algorithm.P6588;

import java.io.*;
import java.util.ArrayList;
import java.util.List;

public class P6588 {
    static boolean play = true;
    static boolean[] numbers = new boolean[1000001];
    static List<Integer> primes = new ArrayList<>();
    static StringBuilder sb;
    static Integer n;

    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("src/Algorithm/P6588/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        sb = new StringBuilder();

        makePrime();

        while (play) {
            n = Integer.parseInt(br.readLine());
            if (n == 0) {
                play = false;
                System.out.println(sb);
                break;
            }
            // System.out.println("n = " + n);
            solveGoldbach(n);
        }
    }

    private static void solveGoldbach(Integer n) {
        // 8 = 3 + 5
        // 8 - 5 = 3
        for (int i = 0; i <= n; i++) {
            if (numbers[n - primes.get(i)]) {
                sb.append(n)
                        .append(" = ")
                        .append(primes.get(i))
                        .append(" + ")
                        .append(n - primes.get(i))
                        .append("\n");
                return;
            }
        }
        sb.append("Goldbach's conjecture is wrong.");
    }

    private static void makePrime() {
        for (int i = 0; i < numbers.length; i++) {
            numbers[i] = true;
        }
        for (int i = 2; i < numbers.length; i++) {
            if (numbers[i] == false) {
                continue;
            }
            primes.add(i);
            for (int j = 2 * i; j < numbers.length; j += i) {
                numbers[j] = false;
            }
        }
    }
}