백준 17103번 : 골드바흐 파티션

게시 2023/10/23

By Jeremiah Lee 10 분 : 읽는 시간

이전 문제인 베르트랑 공준은 단순히 에라토스테네스의 체 알고리즘을 사용하여 소수를 빠르게 구한 다음, n과 2n 사이의 소수를 구하는 문제였기 때문에 특별히 추가된 점이 없어 기록하지 않는다.

이번 문제 골드바흐 파티션은 처음 보았기 때문에 소수를 어떻게 하라는건지 단번에 이해하지 못했지만, 이내 짝수의 소수를 두 개 합하면 그 수가 된다는 것을 금방 알게 되었다.

골드바흐 파티션은 골드바흐의 추측에 기인한 문제이다.

우선 이 문제를 풀기위해서는 골드바흐의 추측을 알고리즘으로 풀어낼 수 있어야한다.
다만, 이 골드바흐의 추측은 아직 풀리지 않은 문제이기 때문에 문제에서 제시된 최댓값을 기준 잡아 활용해야한다.

  
import java.util.Arrays;

public class GoldbachPartition {
    public static void main(String[] args) {
        int n = 1000000;
        boolean[] isPrime = new boolean[n + 1];
        Arrays.fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;

        // 에라토스테네스의 체를 사용하여 소수 구하기
        for (int i = 2; i <= Math.sqrt(n); i++) {
            if (isPrime[i]) {
                for (int j = i * i; j <= n; j += i) {
                    isPrime[j] = false;
                }
            }
        }

        // 골드바흐 파티션 찾기
        for (int evenNum = 4; evenNum <= n; evenNum += 2) {
            boolean foundPartition = false;
            for (int num1 = 2; num1 <= evenNum / 2; num1++) {
                int num2 = evenNum - num1;
                if (isPrime[num1] && isPrime[num2]) { // 두 수가 모두 소수인 경우
                    System.out.println(evenNum + " = " + num1 + " + " + num2);
                    foundPartition = true;
                    break;
                }
            }
            
            if (!foundPartition) { // 골드바흐 파티션이 없는 경우
                System.out.println("Goldbach partition not found for: " + evenNum);
            }
        }
    }
}

문제에서 최대값이 1,000,000이라고 제시되었기 때문에 우선 에라토스테네스의 체를 사용해 100만까지 소수를 구한다.

그 다음으로 골드바흐의 추측을 표현한 골드바흐의 파티션을 구하면 되는데, 해당 알고리즘의 흐름은 다음과 같다.

골드바흐의 추측은 “2보다 큰 모든 짝수는 두 개의 소수로 표현 가능하다”가 기본이기 때문에 파티션을 찾기 위한 시작 수는 4이다.
foundPartition 변수를 사용하여 골드바흐 파티션이 있는지 여부를 추적한다.
num1 변수를 2부터 evenNum/2까지 반복하면서, 가능한 모든 첫 번째 소수(num1)에 대해 두 번째 소수(num2)를 계산한다.
계산된 두 수(num1, num2)가 모두 소수인 경우, 다시 말해 isPrime[num1]과 isPrime[num2]가 모두 참인 경우에는 골드바흐 파티션이 존재하는 것이므로 해당 결과를 출력하고 foundPartition 값을 true로 변경한다.
만약 내부 반복문이 종료되었는데 골드바흐 파티션이 없다면 해당 짝수에 대한 결과를 출력한다.

이런 식으로 해당 짝수에 대한 모든 골드바흐 파티션을 구할 수 있다.

이제 골드바흐 파티션을 구하는 방법을 알았으니, 이 알고리즘을 현재 문제를 풀기 위해 적용해야한다.

우선, 1,000,000까지라는 최댓값이 주어졌기 때문에 에라토스테네스의 체를 사용하여 먼저 이 최댓값까지의 소수를 구해준다.

  
        StringBuilder sb = new StringBuilder();
        int max = 1000000;

        boolean[] isPrime = new boolean[max + 1];
        isPrime[0] = isPrime[1] = true;
        for (int i = 2; i <= Math.sqrt(max); i++) {
            if (!isPrime[i]) {
                for (int j = i * i; j <= max; j += i) {
                    isPrime[j] = true;
                }
            }
        }

그 다음으로 문제에서는 각 입력된 짝수의 골드바흐 파티션 개수를 구하는 문제이기 때문에 골드바흐 파티션을 구하는 알고리즘에서 조금 변형이 필요하다.

  
        while (t > 0) {
            int n = Integer.parseInt(br.readLine());
            int count = 0;
            for (int i = 2; i <= n/2; i++) {
                int num = n - i;
                if (!isPrime[i] && !isPrime[num]) {
                    count++;
                }
            }
            sb.append(count).append('\n');
            t--;
        }
        System.out.println(sb);

여기서 t는 초기에 입력된 짝수의 개수이다.

우선 개수를 세어 줄 count 변수를 선언한다.
아까 보았던 골드바흐 파티션을 구하는 알고리즘을 사용한다. 단, 범위는 주어진 짝수로 알 수 있으므로 기존 알고리즘에서 모든 100만까지의 모든 짝수를 구하는 반복문은 제외한다.
그 다음 파티션을 출력하는 코드에서 count++로 변경하여 개수를 세어준다.
파티션을 구하는 반복문이 끝나면 현재 입력된 짝수의 파티션 개수를 StringBuilder에 합쳐준다.
t–로 반복문을 제어한다.

코드의 흐름은 위와 같다.

이후 마지막으로 개수 전체를 출력해주면 정답이 된다.

전체 소스코드는 다음과 같다.

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

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

        int t = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        int max = 1000000;

        boolean[] isPrime = new boolean[max + 1];
        isPrime[0] = isPrime[1] = true;
        for (int i = 2; i <= Math.sqrt(max); i++) {
            if (!isPrime[i]) {
                for (int j = i * i; j <= max; j += i) {
                    isPrime[j] = true;
                }
            }
        }

        while (t > 0) {
            int n = Integer.parseInt(br.readLine());
            int count = 0;
            for (int i = 2; i <= n/2; i++) {
                int num = n - i;
                if (!isPrime[i] && !isPrime[num]) {
                    count++;
                }
            }
            sb.append(count).append('\n');
            t--;
        }
        System.out.println(sb);
    }
}

참고로 원래는 while 문 안에 각 짝수의 소수를 구하는 에라스토테네스의 체를 함께 삽입했었는데, 시간 소요가 432ms로 너무 오래 걸려서 최댓값까지의 소수를 한 번에 구하고서 푸는 방식으로 변경했다.
쉽게 말해, 에라스토테네스의 체를 while 문 바깥으로 배치했다는 얘기이다.

단계 별로 풀어보기의 뒤쪽에 접근해서 그런지 이제는 특정 알고리즘을 알지 못하면 풀기 굉장히 어렵거나 거의 불가능한 문제들이 많다.
하지만 덕분에 많은 알고리즘을 알게되어가고 있어서 만족스럽다.

또, 이전 네이버 블로그 시절에 작성하던 코테 기록보다 발전하고 있다는 것이 느껴진다.
우선은 부분 적으로 알고리즘을 살펴보는 접근 방식이 마음에 들고 단순히 전체 코드만 들고 코드의 흐름을 분석하는 것보다 하나씩 끊어서 보는 것이 이해에도 좋은 것 같다.
이러한 방식은 티스토리 블로그인 stranger’s lab에서 참고한 방식이다.
백준 코드에 대한 정리가 많다보니 볼 기회가 잦기도 하고 정리가 잘 되어 있어서 참고했다.

다만 아쉬운 점은 프론트 기술을 아예 모르는데 이 블로그가 프론트 기술로 만들어져서 자잘하게 수정하기가 어렵다는 점이 있다.
그래도 그때그때 수정하고는 있다.
그런데 폰트도 좀 변경해야겠다.

알고리즘, 백준

알고리즘 백준

인기 태그