[백준/BOJ] 1644번 소수의 연속합

www.acmicpc.net/problem/1644

1644번: 소수의 연속합

수학 + 투 포인터 문제였습니다.

 

새롭게 알게된 점

연속된 값들을 이용하여 풀어나가는 문제에서 한 배열에 포인터 변수 2개를 두어 탐색하는 투 포인트 알고리즘을 쓸 수 있다.

이때 투 포인트 알고리즘의 시간복잡도는 O(N)이다.

 

에라토스네스의 체 알고리즘을 이용하여 소수를 모두 구해 prime 벡터에 값을 넣어 준 후, prime 벡터에 head와 tail 2개의 포인터 변수를 둬서 투 포인터 탐색을 통해 n을 만들 수 있는 경우를 모두 구하면 됩니다.

 

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

void eratos(int n, vector<int> &v, vector<int> &prime) {
    for(int i = 2; i <= n; i++) {
        v[i] = i;
    }
    
    for(int i = 2; i <= n; i++) {
        if(v[i] == 0) continue;
        for(int j = 2*i; j <= n; j += i) {
            v[j] = 0;
        }
    }
    
    for(int i = 2; i <= n; i++) {
        if(v[i] != 0) prime.push_back(v[i]);
    }
} 

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int n, answer = 0;
    cin>>n;
    vector<int> v(n + 1);
    vector<int> prime;
    
    eratos(n, v, prime);
    
    // 투 포인터
    int head = 0, tail = 0, sum = 0;
    while(1) {
        if(sum > n) sum -= prime[head++];
        else if(tail == prime.size()) break;
        else sum += prime[tail++];
        if(sum == n) answer++;
    }
    
    cout<<answer;
}