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

문제 - 소수의 연속합 (Gold3)

[백준 1644] https://www.acmicpc.net/problem/1644

풀이 전략

• 에라토스테네스의 체와 투포인터의 원리 이용
• 입력한 값과 두개의 포인터가 가리키는 값 사이의 모든 값을 더한 값이 같으면 count++
• 두 개의 vector를 선언해서 하나는 에라토스 테네스의 체를 적용하기 위한 용도, 다른 하나는 합을 구하기 위해 걸러진 소수들을 저장하는 용도로 사용

참고

에라토스테네스의 체

=> 특정 범위 내의 소수를 찾는데 효율적인 방법

• Step1 : 1을 제외시킨다.
• Step2 : 2를 제외한 2의 배수를 제거시킨다.
• Step3 : 3을 제외한 3의 배수를 제거시킨다.
• Step4 : 4의 배수는 Step2에서 지워졌으므로 5의 배수로 넘어가서 같은 작업을 반복한다.
• StepN : 위의 작업을 계속 반복하다보면 소수들만 남게 된다.

[나무위키] https://namu.wiki/w/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98%20%EC%B2%B4

투포인터

: 리스트에 순차적으로 접근해야 할 때 2개의 점의 위치를 기록하면서 처리하는 알고리즘이다.
=> 투포인터 알고리즘을 이용해서 특정 구간의 합을 구할 수 있다.

(BOJ1644 예시 中 1)

소스 코드

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

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N;
    cin>>N;

    vector<bool> A(N+1,1);
    vector<int> B;

    A[0]=A[1]=0; // 0과 1은 해당 X

    for(int i=2;i<=sqrt(N);i++){
        if(A[i]==0){
            continue;
        }
        for(int j=i*i;j<=N;j+=i){
            A[j]=0;
        }
    } // 에라토스테네스의 체
    for(int i=2;i<=N;i++){
        if(A[i]==1){
            B.push_back(i);
        }
    } // 소수들만 vector B에 저장

    int sum=0;
    int count=0;
    int right=0, left=0;
    while(1){
        if(sum<N){
            if(right>=B.size()){
                break;
            }
            sum+=B[right];
            right++;
        }else if(sum>N){
            sum-=B[left];
            left++;
        }else if(sum==N){
            count++;
            if(right>=B.size()){
                break;
            }
            sum+=B[right];
            right++;
        }
    } // 위의 예시에서 설명함
    cout<<count<<'\n';
    return 0;
}

결과

결론 / 느낀점

- 결론

: 에라토스테네스의 체와 투포인터를 잘 활용하면 금방 풀 수 있는 문제였다.

- 느낀점

많은 시도를 했었지만, 틀리고나 OutOfBounds 에러가 뜬 이유는 right 포인터가 N과 같을 때 break를 거는 조건을 추가하지 않았거나, 처음에는 자기 자신(N)이 소수인 경우 count++를 해주는 조건을 따로 넣어줬었는데, 그 부분에서 Index 오류가 뜬 것 같다.

• 41일 때
  vector A

vector B
  

-> 이럴 땐 A와 B에 들어가 있는 요소와 그것의 개수를 확인하는 과정을 통해 OutOfBounds 오류의 원인을 파악할 수 있기 때문에 이러한 과정이 중요하다고 느꼈다.