백준 1644번 소수의 연속합

< 백준 1644번 소수의 연속합 - 마포 코딩박 >

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


 입력된 어떤 수 N을 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 출력하는 문제입니다.

문제풀이는 다음과 같습니다.

(1) (코드 11~18)
 에라토스테네스의 체로 4000000 이하의 소수를 구합니다.

(2) (코드 20~36)
 '연속된' 소수들의 합으로 입력된 N 을 나타낼 수 있는 경우의 수를 구합니다.
 '연속된' 수의 합이므로 투포인터를 이용해 과정(1)에서 구해놓은 소수들을 처음부터 끝까지 O(N) 의 시간복잡도로 탐색합니다.

	#include <iostream>
	#include <vector>
	using namespace std;
	#define ll long long
	const int MAX = 4000000;
	int N;
	vector<int> prime;
	bool visited[4000000];
	int sum, ans, s, e;
	int main(){ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	// 에라토스테네스의 체로 소수 구하기
	for (ll i = 2; i < MAX; ++i){
	if(!visited[i]){
	prime.push_back(i);
	for(ll j=2*i; j < MAX; j+=i)
	visited[j] = true;
	}
	}
	cin >> N;
	// 투포인터
	// sum : prime[s] 이상 prime[e] 미만 의 소수의 합
	// 시작시 sum = 0
	while(1){
	if(sum>=N){
	sum -= prime[s];
	s++;
	}
	// sum<N 인데 e 가 끝까지 온 경우
	else if(e == prime.size()) break;
	else{
	sum += prime[e];
	e++;
	}
	if(sum == N) ans ++;
	}
	cout << ans << '\n';
	return 0;
	}

view raw BOJ 1644.cpp hosted with ❤ by GitHub