[BOJ] 1644 소수의 연속합

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

1644번: 소수의 연속합

 

알고리즘: 투포인터, 에라토스테네스의 체

 

시간복잡도: O(N*log(logN))

 

---

접근:

1. 소수 판별 

2. 연속된 합, N 제한(<=4*10^6)

 

-> 1번은 에라토스테네스의 체를 이용하면 O(NloglogN) 만에 해결이 가능하다.

    문제는 2번인데, 구간 합 문제라고 생각하고 i~j까지 모든 조합을 계산하면, O(N^2)으로 TLE를 받게 된다.

   

 

여기서 주목할 점은 연속된 합.

1번 과정을 통해 소수들을 찾으면, 이들은 오름차순으로 정렬되어있다.

 

$$2,\ 3,\ 5,\ ,\ ...\ ,\ p_i,\ p_{i+1},\ p_{i+2},\ ...$$

$$N=p_i+p_{i+1}+p_{i+2}로\ 표현이\ 가능하다고\ 해보자$$

$$이\ 다음으로\ 가능한\ 조합은\ p_i를\ 포함하지\ 않을\ 것이다.$$

$$또한,\ p_i를\ 제외했으므로\ 합이\ N이\ 되려면\ 적어도\ p_{i+3}은\ 포함해야\ 할\ 것이다.$$

 

이것이 투포인터 알고리즘의 핵심적인 아이디어이다.

모든 가능한 수를 볼 필요 없이, 두 지점을 차례로 움직이면서 해답을 찾아간다.

(이 문제에선 연속합의 시작점과 끝점을 두 지점으로 두면 된다)

 

따라서, 연속합의 시작점을 s라 두고 끝점을 e로 둔 후,

 

1) s~e 합 == N

  : s++, e++

2) s~e 합 > N  (합이 N을 넘어갔으므로, 맨 앞의 수를 제외해봄)

  : s++

3) s~e 합 < N  (합이 N보다 적으므로, 맨 뒤의 수를 추가해봄)

  : e++ 

 

이런 방식으로 가능한 가짓수를 확인해보면 된다.

 

// 1644: 소수의 연속합
// fail 1: while e < p.size() 조건문 추가
#include<iostream>
#include<cmath>
#include<vector>
using namespace std;

int N, s = 1, e = 1, cnt;
bool chk[4000001];
vector<int> p;	// prime number
int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> N;
	
	for (int i = 3; i <= sqrt(N); i+=2)
	{
		if (chk[i]) continue;
		for (int j = (i<<1); j <= N; j += i)
			chk[j] = 1;
	}
	
	p.push_back(0); p.push_back(2);
	for (int i = 3; i <= N; i+=2)
	{
		if (!chk[i])
		{
			p.push_back(p.back() + i);
		}
	}
	
	while (e - s >= 0 && e < p.size())
	{
		if (p[e] - p[s-1] == N)
		{
			cnt++; s++; e++;
		}
		else if (p[e] - p[s-1] < N)
			e++;
		else
			s++;
	}
	
	cout << cnt;
	return 0;
}