백준 1644- 소수의 연속합 : 에라토스테네스의 체, 투 포인터 알고리즘

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

문제

하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수들이 있다. 몇 가지 자연수의 예를 들어 보면 다음과 같다.

• 3 : 3 (한 가지)
• 41 : 2+3+5+7+11+13 = 11+13+17 = 41 (세 가지)
• 53 : 5+7+11+13+17 = 53 (두 가지)

하지만 연속된 소수의 합으로 나타낼 수 없는 자연수들도 있는데, 20이 그 예이다. 7+13을 계산하면 20이 되기는 하나 7과 13이 연속이 아니기에 적합한 표현이 아니다. 또한 한 소수는 반드시 한 번만 덧셈에 사용될 수 있기 때문에, 3+5+5+7과 같은 표현도 적합하지 않다.

자연수가 주어졌을 때, 이 자연수를 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000)

출력

첫째 줄에 자연수 N을 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 출력한다.

 

 

 

에라토스테네스의 체

소수일 때 그 소수를 제외하고 그 소수의 모든 배수를 소수가 아닌 것으로 체를 걸러내듯이 처리한다. 

 

먼저 모두 소수라고 설정한뒤, 

소수가 아닌 수들을 걸러가기 시작한다. 

 

i에 대해 자기자신을 제외한 자신의 배수들에 대해 소수가 아님을 기록한다.

이미 소수가 아니라면 건너뛰는 작업을 통해서 시간의 효율성을 극대화한다.

for i <- 2 to N
   for j <= i * 2 to N; j+i {i의 배수: 2배수부터}
   		if(prime[j] = 0)
        	 	continue;
        prime[j] = 0;

 

 

소수들을 모두 구했다면, 연속된 소수의 합이 주어진 N의 값과 같은지 확인하기 위해 투포인터를 수행한다. 

 

투포인터

본론부터 말하자면 연속된 부분합을 구하되, 그 부분합이 원하는 합과 일치한다면 개수를 증가시키는 것이다.

구현방안은 2개의 포인터를 이용해서 처음, 마지막 원소를 가리키게 해서 해당 원소들 사이의 합을 부분합으로 사용하는 것이다. (누적합을 사용하기도 한다.)

 

이떄 중요한 점은 더하려는 배열들이 오름차순 (혹은 내림차순 - 구현이 살짝 다르겠다) 정렬되어있어야 한다는 점, 그리고 시작점, 끝점이 모두 증가한다는 점이다.

작은 수부터 큰 수까지 정렬된 배열이 있을 때, 합이 N이 되도록 하려면 어떻게 해야할까?

 

1. start는 0 인덱스를 가리키고, end도 0 인덱스를 가리킨다. (초기화)

2-1. start-end 사이의 구간합이 N보다 작다면 end를 1 증가시킨다. (뒤로 갈수록 배열 요소의 크기가 커지므로 구간합이 커지는 효과)

2-2. start-end 사이의 구간합이 N보다 크거나 같다면 start를 1 증가시킨다. (N보다 크다면 요소자체를 하나 빼주고 다음 지점부터 탐색하는 것이다. )

3. 구간합이 N과 같았다면 개수를 1 증가시킨다. 

 

 

2-2과정에서 start를 증가시키고 end는 아무것도 해주지 않기 때문에, 혹시나 놓치는 게 있을까봐 불안해진다. 

브루트포스처럼 end를 초기화시키지 않아도 되는 것일까? 라는 의문이 남기 때문이다.

 

합 M을 만족하기 위해

이미 M보다 큰 부분합을 가진 [start - end] 사이의 구간을 찾았다고 해보자.

이때 start를 증가시키게 되면, [start+1 - end] 사이의 구간은 위에서의 구간보다 작을 수 밖에 없다.

오름차순으로 정렬된 구간에서 찾기 때문에 [start - end] 구간이 M보다 큰 구간일 뿐만 아니라,

start가 같다고 가정하고 합이 M보다 큰 구간을 나열했다고 쳤을 때 '처음으로' 등장한 구간이기 때문이다. 

 

다시말해서  end를 하나 줄인 상황 [start - end-1]은 반드시 M보다 작았을 상황이다.

[start- end-1] < M이라서  [start -1 ~ end -1] 도 반드시 M보다 작을 것이고,

[start -1 ~ end]  구간에서부터 합이 M이상인 구간을 찾아도 문제가 없는 것이다. 

 

 

투 포인터에 대한 설명은 여기를 참고했다.

 

구현한 코드는 다음과 같다. 

 

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
#define FAST std::ios::sync_with_stdio(0); std::cin.tie(0);
#define INF 2147483647
long long N, K;
long long nums[100];
vector<int> primes;
int dp[4000001] = {0,};
int psum[4000001] = {0,};


void setPrime(){ 
    //N이하의 소수 구해두기
   for(int i = 2; i <= N; i++){
        dp[i] = 1;
   }

   for(int i = 2; i <= N; i++){
        for(int j = i*2; j <= N; j+=i){
            if(dp[j] == 0)
                continue;
            dp[j] = 0;
        }
   }

    int idx = 0;
    //소수들 누적합 계산하기, 소수만 따로 저장하기
   for(int i = 2; i <= N; i++){
        if(dp[i] != 0){
            primes.push_back(i);
            if(idx == 0)
                psum[idx] = i;
            else
                psum[idx] = psum[idx - 1] + i;
            idx++;
        }  
   }

}
//2 3 5 7 11 13 17 19
//
int getSum(int s, int e){
    // 누적합을 이용해서 부분합 구하기
    if(s == 0)
        return psum[e];
    return psum[e] - psum[s-1];
}

int countSumSameAsN(int n){
    int start = 0;
    int end = 0;
    int sum = 0;
    int count = 0;
    while(start < primes.size()){
        sum = getSum(start ,end);
        // cout << start << "s e" << end << "\n";
        // cout << "sum : " << sum  << "\n";
        if(sum >= n){
            start++;
        }
        else{
            end++;
        }
        if(sum == n){
            count++;
        }
        
    }

    return count;
}

int main(){
    FAST

    cin >> N;
    long long count = 0;
    setPrime();
    cout << countSumSameAsN(N);
    
}