백준 1644 - 소수의 연속합 (c++)

문제 출처 : https://www.acmicpc.net/problem/1644

 

<접근 방법>

우선 N의 최대값인 4백만까지의 소수들을 구합니다.

그 후, 투 포인터를 이용해서 합이 N이 되는 경우를 세려 주면 될 것 같습니다.

 

<풀이>

1. 에라토스테네스의 체를 이용해서 4백만까지의 소수를 구해서 vector에 저장합니다.

2. 벡터의 제일 앞 0번째 인덱스를 가리키는 변수 두 개를 선언해주고 합을 저장하는 변수도 선언해줍니다.

3. 투 포인터 알고리즘을 이용하여 sum이 N보다 크거나 같으면 sum에 p1이 가리키는 값을 빼고 p1을 한 칸 뒤로 N보다 작으면 p2가 가리키는 값을 더하고 p2를 한 칸 뒤로 이동시킵니다. 그중 sum과 N이 같으면 result++를 해줍니다.

4. p2가 Vec의 범위를 벗어나거나 p1이 p2보다 커지면 반복문을 종료합니다.

 

<소스 코드>

#include <iostream>
#include <vector>
#define MAX 4000001
 
using namespace std;
 
int main() {
  int N, result=0;
  bool check[MAX]={0};
  vector<int> Vec;
  
  cin >> N;
  for(int i=2; i*i<=N; i++){
    if(!check[i]){
      for(int j=i*i; j<=N; j+=i){
        check[j]=true;
      }
    }
  }
 
  for(int i=2; i<=N; i++){
    if(!check[i]) Vec.push_back(i);
  }
  
  int p1=0, p2=0, sum=2;
  while(p1<=p2&&p2<Vec.size()){
    if(sum>=N){
      if(sum==N) result++;
      sum -= Vec[p1];
      p1++;
    }
    else{
      p2++;
      sum += Vec[p2];
    }
  }
 
  cout << result;
}

 

<후기>

처음에 코드를 작성할 때 sum을 Vec[0]으로 초기화했었는데, 값이 한 개 일 때 Vec에 값이 push 되지 않는데 Vec[0]에 접근하려고 해서 런타임 에러 발생했었습니다. 분명 범위를 제대로 지정했는데 OutOfBounds가 뜨길래 질문 게시판을 뒤져보니 저랑 같은 실수를 하신 분이 계시더군요ㅎㅎ...

뭐 그 외에는 에라토스테네스의 체와 투 포인터 알고리즘을 사용할 줄 안다면 크게 어렵지 않은 문제였습니다.