[백준][C++] 1544 소수의 연속합

www.acmicpc.net/problem/1644

1644번: 소수의 연속합

 

 

 

알고리즘 종류

    - 투 포인터

    - 에라토스테네스의 체

 

 

사고 과정

    1. 에라토스테네스의 체로 소수만 선별하기

    2. 선별된 소수 배열에 투 포인터

 

 

 

구현(C++)

#include <iostream>
#include <vector>
#include <cmath>
 
using namespace std;
 
int num;
int answer = 0;
vector<bool> check;
vector<int> primes;
 
 
int main(void){
 
    cin >> num;
    
    check.resize(num+1, true);
    
    // 에라토스테네스의 체  
    for(int i=2; i<=sqrt(num); i++){
        
        if(!check[i]) continue;
        for(int j=i*i; j<=num; j+=i){
            check[j] = false;
        }
    }
    // 소수 값만 옮겨서 저장  
    for(int i=2; i<=num; i++){
        if(check[i]) primes.push_back(i);
    }
    
    // 투 포인터  
    int left=0, right=0;
    int sum=2;
    
    while(left <= right && right < primes.size()){
 
        if(sum == num) { 
            answer ++;
            sum -= primes[left];
            left++;
        }
        else if(sum < num){
            right++;
            sum += primes[right];
        }
        else if(sum > num){
            sum -= primes[left];
            left++;
        }
    }
    
    cout << answer << endl;
}
 
 
 

 

 

시행착오

    - 에라토스테네스의 체를 함수로 만들어서 모든 수를 소수로 판별하는 용도로 사용했다. 그래서 입력된 값에 대한 것만 진행하면 시간복잡도가 log log n인데 n개를 모두 해서 n log log n으로 시간이 크게 되었다. 너무 느리다는 것을 다른 사람들과 비교해보고 수정했다.