← 문제 풀이 목록

백준 17103: 골드바흐 파티션

/ 6분 분량 / 문제 풀이
#알고리즘#백준#코딩테스트

Silver II 난이도 문제를 C++로 풀이한 내용입니다. 주어진 짝수 N을 두 소수의 합으로 표현하는 방법의 개수를 구하는 문제입니다.

백준 17103: 골드바흐 파티션

Silver II 난이도 문제를 C++로 풀이한 내용입니다. 주어진 짝수 N을 두 소수의 합으로 표현하는 방법의 개수를 구하는 문제입니다.

문제 소개

  • 문제 번호: 17103
  • 제목: 골드바흐 파티션
  • 난이도: Silver_II
  • 사용 언어: C++
  • 실행 시간: 32 ms
  • 메모리: 2924 KB

문제 요약: 첫 줄에 테스트 케이스 수 T가 주어지고, 이후 T개의 짝수 N이 주어집니다. 각 N에 대해 N = p + q (p, q는 소수, p ≤ q)를 만족하는 (p, q) 쌍의 개수를 출력합니다.

접근 방법

문제를 이해: 골드바흐 파티션은 2보다 큰 짝수를 두 소수의 합으로 나타내는 표현입니다. 각 N마다 가능한 쌍의 개수를 세야 합니다.

사용 알고리즘/자료구조: 에라토스테네스의 체로 소수 구하기, 소수 리스트에서 투 포인터로 쌍 찾기.

이 방법 선택 이유: T와 N의 범위(최대 100000)를 고려해 모든 N에 대해 소수를 미리 계산하고, 정렬된 소수 리스트에서 투 포인터로 O(N log log N + T * P log P) 시간으로 처리.

풀이 과정

  1. T개의 N을 입력받아 벡터에 저장.
  2. N들 중 최대값 max를 찾아 max까지의 소수를 에라토스테네스의 체로 계산하고 소수 벡터 primes에 저장.
  3. 각 N에 대해 primes에서 투 포인터 L=0, R=primes.size()-1로 시작:
    • primes[L] + primes[R] == N이면 카운트 증가 후 L++, R--
    • 합 < N이면 L++
    • 합 > N이면 R--
  4. 각 N마다 카운트 출력.

핵심 아이디어: 소수 리스트가 정렬되어 있으므로 투 포인터로 효율적으로 합이 N인 쌍 찾기.

주의할 점: primes[R]가 N보다 작아야 하며, L <= R 조건 유지.

코드 설명

#include<bits/stdc++.h>
using namespace std;

int main(){
    int T;
    cin >> T;
    
    // 1. N들을 다 받는다.
    // 짝수 N들이 들어갈 벡터
    vector<int> Ns(T, 0);
    for(int i = 0; i < T; i++){
        cin >> Ns[i];
    }
    
    // 2. 가장 큰 N을 가지고, N-2까지의 소수들을 모두 구하여 벡터에 모두 저장한다.
    int max = *max_element(Ns.begin(), Ns.end());
    vector<bool> isPrime(max + 1, true);
    isPrime[0] = isPrime[1] = false;
    
    for(int i = 2; i * i <= max; i++){
        if(isPrime[i]){
            for(int j = i * i; j <= max; j += i)
                isPrime[j] = false;
        }
    }

    vector<int> primes;
    for(int i = 2; i <= max; i++){
        if(isPrime[i])
            primes.push_back(i);
    }
    
    // 3. 각 N들에 대해 소수 벡터에서 2부터 N보다 작은 소수들까지의 범위를 초기범위로 해서 투 포인터로 합이 N인 경우 카운트
    for(const int& N : Ns){
        
        /*
        int i = 1;
        for(i = 1; primes[i] < N; i++){}... 각 N에 맞게 투포인터에서 R이 되어줄 소수벡터에서의 i를 찾는 건 사치일지도 모른다. R을 size로 주고 각 N들을 투 포인터에게 맡겨보자.
        */
        
        // 이 시점에서 prime[i]가 투포인터의 R이 된다.
        // L은 prime[1]이다.

        // 투포인터 시작
        int L = 0, R = (int)primes.size() - 1;
        int N_partition_cnt = 0;
    
        while (L <= R) {
            int sum = primes[L] + primes[R];
        
            if (sum == N) {
                N_partition_cnt++;
                L++;
                R--;
            } else if (sum < N) {
                L++;
            } else { // sum > x
                R--;
            }
        }
    
        cout << N_partition_cnt << '\n'; 
    }
    
    
    // 골드바흐 파티션: 2보다 큰 짝수를 두 소수의 합으로 나타내는 표현
    /*
    6 3 3
    8 3 5 
    10 3 7, 5 5
    12 5 7 
    100 ...
    */
    //   파티션의 개수!
}

주요 부분 설명:

  • 에라토스테네스의 체: i*i <= max까지 배수 제거.
  • 투 포인터: L, R 이동으로 합 == N인 쌍만 카운트, p ≤ q 보장.
  • 코드 주석: 풀이 단계와 시행착오 기록(각 N별 R 최적화 대신 전체 primes 사용).

예시: N=10일 때 primes에서 (3,7), (5,5) 두 쌍 발견.

복잡도 분석

  • 시간 복잡도: 에라토스테네스의 체 O(max log log max) + primes 생성 O(max) + T * O(P) (P는 소수 개수 ≈ max/ln max) = O(max log log max + T * max/ln max)
  • 공간 복잡도: O(max) (isPrime, primes 벡터)

배운 점

에라토스테네스의 체 최적화(i*i부터 시작), 정렬된 배열에서 투 포인터 적용, 시행착오를 주석으로 기록해 디버깅 효율화.