백준 1644번 - 소수의 연속합 (C++, 에라토스테네스의 체, 누적합, 투포인터)

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

 

아주 어려운 문제는 아니나, 에라토스테네스의 체, 누적합, 투포인터라는 삼박자를 알고 있어야 풀 수 있는 문제였다. 

에라토스테네스의 체 문제를 연속으로 풀다보니 대체 고대 그리스의 철학자들은 얼마나 천재인건가 가늠도 안된다. 

 

아무튼 문제는 다음과 같은 단계로 이루어진다.

 

1. 에라토스테네스의 체를 사용해 소수 판별

2. 누적합을 통해 각 소수의 범위 prefix 배열 처리

3. 투포인터를 활용해 연속합중 N과 같은 것들 처리 

 

https://tigerfrom2.tistory.com/433

알고리즘 - 에라토스테네스의 체(C++)

 

에라토스네테스의 체 개념

 

https://tigerfrom2.tistory.com/468

누적합 알고리즘(1차원, 2차원 누적합)

 

누적합의 개념, 누적합은 2차원에서도 사용 가능하다. 카카오 기출문제 중 2차원 누적합이 있어서 이후 대기업들이 충분히 출제할 수 있다.

 

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

vector<int> primeNumbers;
int prefix[1000000];

void Eratostenes(int N){
    bool check[4000001];

    memset(check, false, sizeof check);
    check[1] = true;
    for(int i = 2; i * i <= N; i++){
        if(check[i] == false){
            for(int j = i*i; j <= N; j += i){
                check[j] = true;
            }
        }
    }
    for(int i = 2; i <= N; i++){
        if(!check[i]){
            primeNumbers.push_back(i);
        }
    }
}

void makePrefix(){
    prefix[0] = 0;
    
    for(int i = 1; i <= primeNumbers.size(); i++){
        prefix[i] = primeNumbers[i - 1] + prefix[i - 1];
    }
}

int solution(int N){
    int answer = 0;
    int lo = 0; int hi = 1;
    while(hi <= primeNumbers.size()){
        int value = prefix[hi] - prefix[lo];

        if(value == N){
            answer++;
            lo++;
            hi++;
        }else if(value < N){
            hi++;
        }else if(value > N){
            lo++;    
        }
    }

    return answer;
}

int main(){
    int N; cin >> N;

    Eratostenes(N);
    makePrefix();
    cout << solution(N) << '\n';
}