[백준] 17103번 : 골드바흐 파티션 (실버 Ⅱ) - Java/자바

---

✅ 문제

문제링크

🔗 https://www.acmicpc.net/problem/17103

 

---

✅ 풀이

🔹 실패한 코드 (시간 초과)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < t; i++) {
            int n = Integer.parseInt(br.readLine());
            sb.append(goldbachPartition(n)).append("\n");
        }
        sb.setLength(sb.length() - 1);
        System.out.println(sb);
    }

    public static int goldbachPartition(int n) {
        int count = 0;
        List<Integer> prime = new ArrayList<>();

        // n보다 작은 소수들을 구한다.
        for (int i = 2; i < n; i++) {
            if (is_Prime(i)) {
                 prime.add(i);
            }
        }

        // 중복 가능, 순서 없이 2개 뽑아서 검사 (중복조합) (n + k - 1)C(k)개 경우
        int size = prime.size();
        for (int i = 0; i < size; i++) {
            for (int j = i; j < size; j++) {
                if (prime.get(i) + prime.get(j) == n) {
                    count++;
                }
            }
        }
        return count;
    }

    public static boolean is_Prime(int num) {
        if (num < 2) return false;
        for (int i = 2; i <= Math.sqrt(num); i++) {
            if (num % i == 0) return false;
        }
        return true;
    }
}

 

이 문제를 접하면서 시간 제한 생각없이 가장 먼저 떠오른 코드이다.

하지만 시간 제한 0.5초를 넘어 시간 초과의 결과를 얻게된 실패한 코드이다.

 

테스트 케이스의 수 t를 입력받고 for문을 통해 t번 반복한다.

n을 입력받고 StringBuilder sb에 goldbachPartition(n)의 반환값을 넣어준다.

sb를 출력한다.

 

goldbachPartition(int n) 메서드

매개변수로 받은 n을 두 소수의 합의 개수를 구하는 메서드로 개수인 count를 int형으로 반환한다.

전체 개수를 알 수 없으므로 가변적으로 하기 위해 List<Integer> prime = new ArrayList<>(); 하여 생성한다.

for문을 n번 반복하고 소수는 1은 아니므로 i = 2부터 시작해 n보다 작은 소수들을 구한다.

is_Prime()메서드의 반환값이 true이면 소수이므로 prime.add(i); 하여 리스트에 추가한다.

 

중복이 가능하고 (2, 7) 이나 (7, 2)는 같은 파티션으로 본다고 문제에서 설명하여서 순서없이 2개 뽑아서 검사하도록 한다.

이는 중복조합으로 이 문제에서는 필요없지만 전체 검사 경우의 수는

$_{n\;}\textrm{H}_{\;k}\;=\;_{n\;+\;k\;-\;1\;}\textrm{C}_{\;k}$

로 생각해볼 수 있다.

 

int size = prime.size(); 하여 사이즈를 저장한다.

for문을 size만큼 반복을 하고 이중 for문을 하여 j = i부터 size 만큼 반복한다.

if문에 prime.get(i) + prime.get(j) == n 조건을 주어 두 소수의 합이 n이면 count++; 하여 개수를 세어준다.

count를 반환한다.

 

is_Prime(int num) 메서드

소수인지 판별해주는 메서드로 boolean을 반환한다.

num이 0 또는 1이면 false를 반환하고 for문을 통해 i = 2 부터 num의 제곱근까지 검사한다.

if문에 num % i == 0 이 true이면 나누어 떨어지는 것이므로 소수가 아니다.

따라서 false를 반환한다.

for문이 모두 끝나면 소수이므로 true를 반환한다.

 

위 코드는 t와 n이 커지면 반복횟수도 많아지므로 시간이 오래걸린다.

따라서 시간을 줄이기 위해 에라토스테네의 체 알고리즘을 사용해 소수를 미리 찾아놓도록 하자.

 

🔹 결과 (실패)

 

🔹 코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();

        // 에라토스테네스의 체 알고리즘으로 소수 찾아놓는다. 소수 = false
        boolean[] isPrime = new boolean[1000001];
        isPrime[0] = isPrime[1] = true;
        for (int i = 2; i * i < isPrime.length; i++) {
            if (!isPrime[i]) {
                for (int j = i * i; j < isPrime.length; j += i) {
                    isPrime[j] = true;
                }
            }
        }

        // 테스트 케이스 시작
        for (int i = 0; i < t; i++) {
            int n = Integer.parseInt(br.readLine());
            int count = 0;

            // 순서만 다른 것은 같은 파티션이므로 n/2 까지만 검사하면 된다.
            for (int j = 2; j <= n / 2; j++) {
                // j + n - j = n 이므로 이 둘이 소수이기만 하면 골드바흐 파티션이 성립한다.
                if (!isPrime[j] && !isPrime[n - j]) {
                    count++;
                }
            }
            sb.append(count).append("\n");
        }
        sb.setLength(sb.length() - 1);
        System.out.println(sb);
    }
}

 

에라토스테네스의 체 알고리즘 사용을 위해 문제에서 n이 2보다 크고 1,000,000보다 작거나 같으므로 boolean 배열 isPrime을 1000001 크기로 생성한다.

인덱스가 각 수를 의미한다.

boolean 배열은 생성되면 기본적으로 false로 초기화 되므로 소수가 아니하면 true로 하고 소수이면 false를 하도록 한다.

0과 1은 소수가 아니므로 true로 해준다.

for문 반복을 i = 2부터 시작해 i * i 가 isPrime.length까지 반복한다.

이는 어떤 수가 소수인지 아닌지 알기 위해서는 2부터 해당 수의 제곱근까지만 확인하면 되기 때문이다.

여기서는 전체크기의 제곱근까지만 거르면 모두 거를 수 있다.

다음 포스팅을 참고하자.

[백준] 1978번 : 소수 찾기 (브론즈 Ⅱ) - Java/자바 (feat : 에라토스테네스의 체)

 

if문 조건으로 !isPrime[i] 하여 해당 인덱스에 false로 되어 있으면 for문 반복을 j = i * i 부터 전체크기까지 i 배수씩 반복한다.

isPrime[j] = true; 하여 배수를 모두 걸러주도록 한다.

 

에라토스테네스의 체 알고리즘으로 소수를 모두 찾아놓았으면 for문을 통해 입력받은 테스트 케이스의 개수 t 만큼 반복하고 n을 입력받는다.

int count = 0;하여 세어줄 개수를 선언한다.

for문을 통해 j = 2 부터 n과 같거나 작을 때까지 반복한다.

if문 조건을 !isPrime[j] && !isPrime[n - j] 하여 합이 n인 두 수가 각각 소수인지 확인하여 맞으면 count++; 하여 세어준다.

StringBuilder sb에 각 테스트 케이스의 count 값을 넣어준다.

sb를 출력한다.

 

에라토스테네스의 체를 사용하면 실행시간을 줄일 수 있었다.

 

🔹 결과

 

🔹 알게된 정보

• 에라토스테네스의 체를 사용해 소수를 미리 찾아놓으면 실행 시간을 줄일 수 있다.
• 합이 n이 되는 두 수 중에 두 수가 소수인지 찾는 방법이 실행 시간을 줄일 수 있다.

 

---