[C++ 백준 문제풀이] 백준 1644: 소수의 연속합

 

 

>>>  풀이 전략   <<<

• N까지의 소수를 모두 구해야함. ( 아리스토텔레스의 채 사용 )
• 연속된 소수의 합으로 나타낼 수 있는 경우들을 Count 해야 함 ( >> 투포인터 알고리즘 활용 )

 

#include <iostream>
#include <vector>
#include <math.h>

int main() {
	std::ios::sync_with_stdio(0);
	std::cin.tie(0);

	int n;
	std::cin >> n;

	std::vector<int> list(n+1);
	std::vector<bool> numList(n + 1);

	int num = 0;
	for (int i{ 2 }; i <= sqrt(n); i++) {
		if (numList[i] == true) continue;
		for (int j{ 2 }; j*i <= n ; j++) {
			numList[i * j] = true;
		}
	}
	for (int i{ 2 }; i <= n; i++) {
		if (!numList[i]) {
			list[num++] = i;
		}
	}

	int s = 0;
	int e = 0;
	int ans = list[e];
	int count = 0;
	while(s < num && e < num) {
		if (ans > n) {
			ans -= list[s++];
		}
		else if (ans < n) {
			ans += list[++e];
		}
		else {
			count++;
			ans -= list[s++];
		}
	}

	std::cout << count << "\n";
}

 

> 투포인터 알고리즘은 부분합 알고리즘의 심화버전이라는 생각이 든다.

> '연속된' 조건과 구간의 합을 구한다는 상황이 겹친다.