문제 url:
골드바흐 파티션
문제:
🤔 문제 알아보기
골드바흐 추측.. 이름부터가 아주 풀기 싫게 생겼다. 하지만 문제를 읽어보면 특별히 내용이 어렵지 않다.
골드바흐의 추측, 2보다 큰 짝수는 두 소수의 합으로 나타낼 수 있다.
먼저, 입력받은 수의 소수를 구하고, 두 소수간의 합이 입력받은 수와 같으면 우리는 그걸 골드바흐 파티션이라 부른다.
TC 중 10을 살펴보면
10의 소수에는 2,3,5,7이 존재한다. 그중 우리는 3, 7 / 5, 5 이렇게 두 쌍이 두 수의 합이 10이 되는 소수이다.
자 저 숫자들을 보니깐 뭔가 떠오르지 않은가?
3+ 7 = 10 -> 10 - 3 = 7 , 5 + 5 = 10 -> 10 - 5 = 5
필자는 입력값을 num, 소수를 n이라고 지칭해서 설명하자면,
n과 num - n 이 소수라면 우리는 이 쌍을 골드바흐의 파티션이라고 할 수 있는 것이다.
또한, 소수를 구하기 위해 반복을 할 것인데, 반복은 num / 2만큼만 하면 될 것이다.
왜? num / 2 값 이상으로 더하게 되면 n과 같기는 커녕 n을 넘길것이기 때문이다.
쉽게 말하자면, 10처럼 5,5로 딱 절반값들의 합이 n이 되는 경우가 존재한다.
그럼 7, 3은? 이미 이전에 3, 7로 계산했기 때문에 의미가 없다.그래서 반복을 num / 2만큼 하면 되는 것이다.
자 여기까지 풀이를 생각해볼 수 있었고,
이제 문제 조건을 조금 알고 가자면, 시간 제한이 0.5초이다. 문제가 아주 사고났다.. 시간이 너무 짜다 짜 메모리 제한은 😁 어쨋든, 최대한 연산을 적게 생각해야 풀 수 있다.
그래서 우리는 에라토스테네스의 체를 활용하고자 한다. 에라토스테네스의 체는
O(N loglogN)의 시간복잡도를 가진다. chatgpt가 그랬다
그래서 1백만 값을 넣어도 31,622,776.6 (3천1백만) 연산을 수행할 뿐이다.
필자가 간단히 계산하는 방법이 있다. 1초는 1억연산, 그렇다면 0.5초는 5천만 연산까지 가능할 것이다.
🐱👤 실제 코드
import java.io.*;
import java.util.ArrayList;
import java.util.List;
public class Main {
static boolean[] prime_num;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sbd = new StringBuilder();
// 소수 찾기 함수 호출
getPrime();
int tc = Integer.parseInt(br.readLine());
for(int k = 0; k < tc; k++) {
int n = Integer.parseInt(br.readLine());
int cnt = 0;
for(int i = 2; i <= n/2; i++) {
if(!prime_num[i] && !prime_num[n - i]) {
cnt++;
}
}
sbd.append(cnt).append("\n");
}
System.out.println(sbd);
}
static void getPrime() {
// n+1을 하는 이유는 0이 포함되기 때문
// n이 백만인 이유는 문제 조건에서 n이 1백만 이하까지 올 수 있다 했기 때문
prime_num = new boolean[1000001];
//0과 1은 소수가 아니므로 true를 선수로 초기화
prime_num[0] = true;
prime_num[1] = true;
// i는 배수를 의미하는데, 소수는 2<= p <= sqrt(n)의 소수로
// n을 p로 나누었을 떄, 떨어지면 n는 소수가 아니고, 안 떨어지면 n는 소수이다.
for(int i = 2; i <= Math.sqrt(prime_num.length); i++) {
// 이것이 체의 역할로, true(소수아님)이면 아래 로직을 건너뛰기
if(prime_num[i]) {
continue;
}
// i의 배수에 대한 n까지의 숫자로,
// 해당 값들은 소수가 아니기 때문에 true를 반환
// 단 i의 배수 2, 3.. 11,.. 자체는 소수이기 때문에
// j의 가장 작은 배수값이 i * i가 된다. (그 이전 값들은 이미 걸러졌기 때문)
// 브루트 포스때와 같이 나머지가 0일 경우 소수가 아닌 로직은 필요 없는 것,
for(int j = i * i; j < prime_num.length; j = j + i) {
// i가 2라고 하면, 4,6,8,..은 전부 2로 나누어 떨어지기 때문에
// 소수가 아니다.
prime_num[j] = true;
}
}
}
}
여기서 getPrime()메서드를 통해 소수를 구하는데, 이것을 왜 함수로 빼서 계산해놓은 이유는 tc를 반복할 때마다 에라토스테네스의 체를 계산하게 되면
아까 말햇듯 1백만이 들어오면 3천백만의 연산횟수를 가지게 될 것이다.
그럼?? 시간이 무조건 부족할 수 밖에 없다.
그래서 먼저 가장 큰 수로 들어올 수 있는 1백만수 이하의 소수를 구해놓는 것이다.
다른 내용은 주석과 위의 문제 알아보기로 알아본 내용이기에 따로 설명하지 않겠다.
💢 트러블 슈팅
3번의 시간 초과가 있었다.
처음에는 TC안에 에라토스테네스의 체를 구현하였으며, 이를 TC만큼 반복
또한 골드바흐 파티션을 구하기 위해 2중for문을 이용해 브루트포스 알고리즘 형식으로 푼 것
-> 이건 무조건 시간 초과가 나올 수 밖에 없었다..
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sbd = new StringBuilder();
int tc = Integer.parseInt(br.readLine());
for(int k = 0; k < tc; k++) {
int n = Integer.parseInt(br.readLine());
// n+1을 하는 이유는 0이 포함되기 때문
boolean[] prime_num = new boolean[n+1];
//0과 1은 소수가 아니므로 true를 선수로 초기화
prime_num[0] = true;
prime_num[1] = true;
// i는 배수를 의미하는데, 소수는 2<= p <= sqrt(n)의 소수로
// n을 p로 나누었을 떄, 떨어지면 n는 소수가 아니고, 안 떨어지면 n는 소수이다.
for(int i = 2; i <= Math.sqrt(n); i++) {
// 이것이 체의 역할로, true(소수아님)이면 아래 로직을 건너뛰기
if(prime_num[i]) {
continue;
}
// i의 배수에 대한 n까지의 숫자로,
// 해당 값들은 소수가 아니기 때문에 true를 반환
// 단 i의 배수 2, 3.. 11,.. 자체는 소수이기 때문에
// j의 가장 작은 배수값이 i * i가 된다. (그 이전 값들은 이미 걸러졌기 때문)
// 브루트 포스때와 같이 나머지가 0일 경우 소수가 아닌 로직은 필요 없는 것,
for(int j = i * i; j <= n; j = j + i) {
// i가 2라고 하면, 4,6,8,..은 전부 2로 나누어 떨어지기 때문에
// 소수가 아니다.
prime_num[j] = true;
}
}
int cnt = 0;
// 골드바흐는, 두 소수의 합이 n과 같아야 하므로
// 6같은 경우 3, 3만 가능하다.
// 즉 같은값끼리 더할 수 있어야 하기 때문에 y = x를 대입,
// 반복해서 전체 경우의 수를 계산해봐야 하기 때문에 이렇게 for문이 두개,
for(int x = 2; x < prime_num.length; x++) {
for(int y = x; y < prime_num.length; y++) {
if(!prime_num[x] && !prime_num[y]) {
if(x + y == n) {
cnt++;
break;
} else if(x + y > n) { // 이미 n 이상을 넘겼기 때문에 더 볼 필요가 없다/
break;
}
}
}
}
sbd.append(cnt).append("\n");
}
System.out.println(sbd);
}
}
두 번째도 위랑 비슷하지만, 다른점이 있다면 에라토스테네서의 체를 통해 만든 배열에서 소수인 값만 리스트로 뽑아와 해당 리스트로 2중 for문을 제작했다는 점,
-> 이를 통해 연산횟수를 줄일 수 있었지만, 0.5초는 무조건 넘길 수 밖에 없었다.
import java.io.*;
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));
StringBuilder sbd = new StringBuilder();
int tc = Integer.parseInt(br.readLine());
for(int k = 0; k < tc; k++) {
int n = Integer.parseInt(br.readLine());
// n+1을 하는 이유는 0이 포함되기 때문
boolean[] prime_num = new boolean[n+1];
//0과 1은 소수가 아니므로 true를 선수로 초기화
prime_num[0] = true;
prime_num[1] = true;
// i는 배수를 의미하는데, 소수는 2<= p <= sqrt(n)의 소수로
// n을 p로 나누었을 떄, 떨어지면 n는 소수가 아니고, 안 떨어지면 n는 소수이다.
for(int i = 2; i <= Math.sqrt(n); i++) {
// 이것이 체의 역할로, true(소수아님)이면 아래 로직을 건너뛰기
if(prime_num[i]) {
continue;
}
// i의 배수에 대한 n까지의 숫자로,
// 해당 값들은 소수가 아니기 때문에 true를 반환
// 단 i의 배수 2, 3.. 11,.. 자체는 소수이기 때문에
// j의 가장 작은 배수값이 i * i가 된다. (그 이전 값들은 이미 걸러졌기 때문)
// 브루트 포스때와 같이 나머지가 0일 경우 소수가 아닌 로직은 필요 없는 것,
for(int j = i * i; j <= n; j = j + i) {
// i가 2라고 하면, 4,6,8,..은 전부 2로 나누어 떨어지기 때문에
// 소수가 아니다.
prime_num[j] = true;
}
}
int cnt = 0;
// 소수인 값들만 가져오기
List<Integer> prime_list = new ArrayList<>();
for(int i = 0; i < prime_num.length; i++ ) {
if(!prime_num[i]) {
prime_list.add(i);
}
}
for(int i = 0; i < prime_list.size(); i++) {
for(int j = i; j < prime_list.size(); j++ ) {
if(prime_list.get(i) + prime_list.get(j) == n) {
cnt++;
break;
}
}
}
sbd.append(cnt).append("\n");
}
System.out.println(sbd);
}
}
세 번째 부터는 답지를 참고한 후 풀었다. 그래서 에라토스테네스의 체도 함수로 만들어 한번만 호출하게 하였지만, num / 2하는 이유를 제대로 안보고 와서 틀렸다.
킁.. 이런 생각을 어떻게 해야 답지를 보지 않고 생각할 수 있을까? 하는 걱정과 함께 이 문제를 푼 모든 분들을 존경하는 마음을 가지게 되었다.
많은 문제를 접하면서 필자도 여러 사고를 가지도록 더 열심히 해봐야 겠다.
💜 참고자료
