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

https://bbty97.tistory.com/manage/newpost/?type=post&returnURL=%2Fmanage%2Fposts%2F 

TISTORY

배수, 약수, 소수 관련 포스팅을 이렇게 많이 할 줄은 몰랐다.. 모두 알고 있는 내용이지만 알고리즘을 어떤 식으로 구현하는지에 따라서 시간 차이가 천차만별인 것을 보고 다각도의 시선이 얼마나 중요한 것인지 다시 한 번 깨닫는다.

 

< 접근 방식 1 - 실패 >

이전 소수 문제에서 썼던 알고리즘인 √n 을 다시 한 번 이용했다.

6을 예로 들면, 2부터 모든 가짓수를 세고 3 + 3 = 6 을 발견해낸다.

어차피 (2, 3) 과 (3, 2)의 순서쌍은 같은 것으로 취급되기에 6의 절반인 3까지만 세면 된다. 가짓수가 많이 줄었으므로 혹시..? 하는 마음에 시도해보았으나 역시 시간초과 ㅠ 아무래도 사중반복문이 되어 어쩔 수 없는 것 같다. 시간 복잡도가 O(n^4)이 되니 당연한 듯 하다.

 

< 접근 방식 2 - 성공 >

이번에는 도저히 모르겠어서 구글의 도움을 받았다. '에라토스테네스의 체' 라는 기법을 쓰길래 살펴보니 먼저 배열을 배정해놓고 시작하는 것이다. 이런 방법이 시간이 많이 걸린 적은 없는 듯. 방법은 간단했다. 배열을 입력값의 범위만큼 먼저 생성하여 초기화 해놓고 2부터 시작해서 그 수의 배수는 배열의 값을 0으로 만들어 결국 소수만 남기는 것이다.

 

출처는 여기. https://velog.io/@max9106/Algorithm-%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98-%EC%B2%B4

[Algorithm] 에라토스테네스의 체

에라토스테네스의 체 구현은 그대로 했고, 골드바흐 파티션 카운트 알고리즘은 약간 다르게 구현했다. 위의 블로그에서는 5 + 5 = 10 과 같이 같은 수가 나오면 하나를 더 카운트 하여 최종적으로 / 2를 해주는 선택을 했고, 나는 위에 기재했던 것처럼 애초에 n / 2 까지만 카운트했다.

 

아래는 코드이다.

 

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>

#define MAX 1000000

using namespace std;

int arr[MAX + 1];

int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

for (int i = 2; i <= MAX; i++) {
arr[i] = i;
}

for (int i = 2; i <= sqrt(MAX); i++) {
if (arr[i] == 0)
continue;
for (int j = i * i; j <= MAX; j += i)
arr[j] = 0;
}

int T;
cin >> T;

int n;
for (int i = 0; i < T; i++) {
int count = 0;
cin >> n;
for (int j = 2; j <= n / 2; j++) {
if (arr[j] + arr[n - j] == n)
count++;
}
cout << count << endl;
}

return 0;
}