[c/c++] 백준 17103(Silver 2)

🔨 문제

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

골드바흐의 추측: 2보다 큰 짝수는 두 소수의 합으로 나타낼 수 있다.
짝수 N을 두 소수의 합으로 나타내는 표현을 골드바흐 파티션이라고 한다. 짝수 N이 주어졌을 때, 골드바흐 파티션의 개수를 구해보자. 두 소수의 순서만 다른 것은 같은 파티션이다.

첫째 줄에 테스트 케이스의 개수 T (1 ≤ T ≤ 100)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 N은 짝수이고, 2 < N ≤ 1,000,000을 만족한다.

각각의 테스트 케이스마다 골드바흐 파티션의 수를 출력한다.

🔨 해결방법

우선 소수를 구하는 문제는 시간초과가 걱정된다면 항상 '에라토스테네스의 체'를 이용해야 한다.

골드바흐의 파티션을 이용하는 문제는 저번에도 풀었어서 의기양양하게 문제에 접근했지만 저번과 마찬가지로 '시간초과'의 늪을 쉽게 빠져나오지 못했다 ㅎ

일단 정답 받은 코드먼저 보자면, 시간초과한 코드와 다르게 for문을 하나만 사용했다. i=2부터 i=N/2까지 돌아가는 for문에서 소수를 판별한 배열이 골드바흐의 파티션에 해당하는지 확인
골드바흐 파티션 확인 방법은 'arr[i]+arr[N-i] == N' 이라면, 개수 체크용 변수를 +1 해줬다.

그 다음 시간초과 코드들은 for문을 두 개 사용했는데 예제는 모두 맞게 나왔지만 시간초과로 정답 코드로 제출되진 못했다. 해당 코드는 주석으로 확인
나는 골드바흐의 파티션을 구하려면 당연하게도 for문을 두 개 사용해야 한다고 생각했다. 근데 for문 하나로도 풀 수 있다는 걸 알 수 있는 문제였다.

아무리 그래도 시간 제한 0.5초 장난하냐?????

🔨 코드

#include <iostream>
using namespace std;

int arr[1000001]={0};  // 소수 판별 저장용 배열
int t, num;    // 입력 받을 변수

void check_Partition(int start){ // 파티션 개수 체크 
    
    int difCnt =0;  // 개수 체크할 변수 초기화
    
	 for(int i=2;i<=start/2;i++){
        if(arr[i]+arr[start-i]==start) difCnt++;
    }

/////////////////////////////////// 시간초과 코드 1
//    for(int i=start/2;i>=2;i--){    // 입력받은 숫자의 중간값부터 1씩 감소
//        if(arr[i]==0) continue; // 소수가 아니라면 skip
//        for(int j = i;j<=start;j++){    // 0이 아닌 i값부터 입력값까지 1씩 증가
//            if(arr[i]+arr[j]>start) break;    // 시간초과 방지(하지만 시간초과 뜸;)
//            if(arr[i]+arr[j]==start) difCnt++;    // 파티션 확인
//        }
//    }

////////////////////////////////// 시간초과 코드 2
//    for(int i=start;i>=start/2;i--){   // 입력받은 값부터 입력값/2 까지 1씩 감소
//        if(arr[i]==0) continue;	// 소수가 아니라면 skip
//        for(int j=2;j<=start/2;j++){	// 2부터 입력값/2까지 1씩 증가
//            if(arr[j]==0) continue;
//            if(arr[i]+arr[j] == start) difCnt++;	// 파티션 확인
//        }
//    }

    cout << difCnt << '\n';
}

int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin>> t;    // 테스트 케이스의 개수 입력

    // 에라토스테네스의 체
    // 1. 배열 생성 후 초기화
    for(int i=2;i<=1000000;i++){
        arr[i]=i;
    }
    // 2. 2부터 시작해서 특정 수의 배수에 해당하는 수를 모두 지움
    for(int i=2;i<=1000000;i++){
        if(arr[i]==0) continue;
        else {
            for(int j=i*2;j<=1000000;j += i){  // 자기 자신 제외하고 배수부터 차례로 제외
                arr[j]=0;
            }
        }
    }

    while(t>0){
        cin >> num;
        check_Partition(num);
        t--;
    }

    return 0;
}