Boj 1644 c++ 소수의 연속합

두 포인터 알고리즘과 에라스토테네스의 체, 두가지 알고리즘을 이용하는 구현 문제였다.

문제의 내용은 다음과 같다.

 

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

다음과 같이 어떤 숫자 n이 주어지면, n 보다 작거나 같은 연속한 소수의 부분합이 다시 n이 되는 경우의 수를 구하는 문제이다.

하지만 특정 수, 예를 들면 20과 같은 경우에는 자기 자신이 나오는 부분합이 아예 존재하지 않을 수 있다. 이러한 경우에는 출력값은 0이다. 

 

이 문제를 해결할 방법은 앞서 풀었던 제곱 ㄴㄴ수와 굉장히 유사하며, 이에 두 포인터의 개념을 덧붙였을 뿐이다. 

우선 에라스토테네스 알고리즘으로 n이하의 소수를 구한 다음, 두 포인터 알고리즘을 사용할 배열에 따로 순서대로 저장한다.

그 후에는 head값과 tail값을 조절해가며 부분합이 n이 되는 경우를 하나하나 세준다. 

 

이때, 구해야 하는 부분합의 값 n과 실제로 더한 값 sum의 대소비교를 통해 head와 tail값의 인덱스를 더해주며, 반복문의 탈출조건은 tail 값이 (배열의 크기-1)보다 커졌을 경우이다.

소수 판정

두 포인터 알고리즘

전체코드

#include<iostream>
#include<vector>
#include<cmath>

using namespace std;



int main(){

    long long n;

    cin>>n;

    vector<long long> prime(n+1, 1);

    prime[0]=prime[1]=0;

    for(int i=2; i*i<=n; i++){

        if(prime[i]==1){
            for(int j=i*i; j<=n; j+=i){
                prime[j]=0;}}
    }
    int cnt=0;

    for(int i=2; i<=n; i++){
        if(prime[i]==1)
            cnt++;
    }

   int index=0;

    vector<long long> point(cnt+1);

    for(int i=2; i<=n; i++){
        if(prime[i]==0) continue;

        point[index]=i;
        index++;

    }
    int tail=0;
    int head=0;
    long long sum=0;
    int ans=0;

    	while (tail <= cnt) {
		if (sum < n) {
			sum += point[tail++];
		} else if (sum > n) {
			sum -= point[head++];
		} else {       //sum==n일 때
		    ans++;
			sum += point[tail++];
		}
	}

	cout<<ans;




}