1644. 소수의 연속합

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

1644번: 소수의 연속합

 

풀이

필요 알고리즘: 에라토스테네스의 체, 투 포인터

 

문제의 요구사항은 연속된 소수의 합으로 자연수 N을 나타낼 수 있는지이다. 이중 for문을 활용하여 \(O(N^{2})\)에 풀 수도 있지만, N의 최댓값 4백만으로는 TLE가 나기 딱 좋으므로 다른 방법을 찾아야 한다. 다행히 연속된 소수의 합이므로 투 포인터로 합계의 범위를 조절하며 확인할 수 있고, 이를 활용하면 \(O(N)\)의 시간 복잡도로 풀 수 있다.

 

먼저 에라토스테네스의 체를 활용하여 N 이하의 소수를 찾는다. 그 후, 투 포인터 first, last를 선언하고(이름은 이렇게 했지만 다 풀고 보니 처음과 마지막이랑은 별로 상관없었다), 모두 0번째 인덱스를 가리키도록 한다. 다음으로 소수의 연속합을 저장하는 변수 sum을 제일 작은 소수(2)로 초기화한다. 그리고 아래와 같은 과정으로 소수의 연속합이 N인지를 확인한다.

1. sum의 값이 N 미만이면 last를 1 증가시킨 뒤 그 인덱스의 값을 sum에 더한다.
2. sum의 값이 N 이상이면 first 인덱스의 값을 sum에 더한 뒤 first의 값을 1 증가시킨다. 추가로 sum과 N의 값이 같으면 출력값을 1 증가시킨다.
3. 위 과정을 first와 last가 N 이하의 소수의 배열의 인덱스를 벗어날 때까지 계속한다.

 

시간 복잡도

에라토스테네스의 체의 시간 복잡도는 \(O(N\log{\log{N}})\)이고, 투 포인터의 시간 복잡도는 \(O(N)\)이다. 따라서 총 시간 복잡도는 \(O(N(\log{\log{N}}+1))\simeq O(N\log{\log{N}})\)이다.

 

소스코드

#include <iostream>
#include <vector>
using namespace std;

int N, ans;
vector<bool> check(4'000'001, true);
vector<int> primes;

// 소수를 찾는 함수
void checkPrime() {
    for(int i = 2; i * i <= N; i++) {
        if(!check[i]) continue;
        
        for(int j = i * 2; j <= N; j += i) {
            check[j] = false;
        }
    }
    
    for(int i = 2; i <= N; i++) {
        if(check[i]) primes.push_back(i);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> N;
    if(N == 1) {
        cout << 0;
        return 0;
    }
    
    checkPrime();
    
    int first = 0, last = 0;
    int psize = primes.size();
    int sum = primes[0];
    primes.push_back(0);	// OutOfBounds 오류를 막기 위한 더미 원소 삽입
    while(first < psize && last < psize) {
        if(sum == N) {
            ans++;
            sum += primes[++last];
        }
        else if(sum > N) {
            sum -= primes[first++];
        }
        else {
            sum += primes[++last];
        }
    }
    
    cout << ans;
    return 0;
}

last의 값을 먼저 증가시킨 뒤 그 인덱스를 참조하기 때문에, 소수가 저장된 벡터 primes의 인덱스를 벗어날 수 있다. 이를 막기 위해 primes에 추가로 더미 원소를 삽입하였다.