[백준] 1664 소수의 연속합

✔️ 문제 링크

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

1644번: 소수의 연속합

---

✔️ 문제 이해

◾ 연속된 소수의 합으로 나타낼 수 있는 자연수 N이 주어진다.

◾ 자연수 N을 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 구해야한다.

◾ 연속된 소수란 다음을 말한다. 2, 3, 5, 7, 11, 13 

◾ 다음은 연속된 소수가 아니다. 2, 3, 5, 7, 11, 17 (중간에 13을 건너뛰고 17이 나왔기 때문)

---

✔️ 설계

◾ 어려운 문제가 아니다. 왜냐하면 에라스토테네스의 체와 투 포인터를 알면 쉽게 풀 수 있는 문제이다.

◾ 에라스토스테네스의 체를 이용하여 N이하의 소수 집합을 구한다. vector<int> primes;

◾ 그 다음 투 포인터 기법을 사용한다. 즉, primes을 for문으로 돌며, 합이 N인 구간의 개수를 찾는다. 투포인터의 시간 복잡도는 O(N)이므로 충분히 빠르다. 

---

✔️ 문제 회고

◾ 에라스토테네스의 체와 투 포인터를 알고 있어서 쉽게 풀었다. 

◾ 투 포인터에 더 익숙해질 필요가 있다. 

---

👨🏻‍💻 소스 코드

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

vector<int> primes;
bool isPrime[4000001] = { false };
int n;

int solve() {

	int cnt = 0;
	int low = 0, high = 0;
	int sum = 0;

	// 투포인터 기법을 사용해 만족하는 구간을 O(N)만에 찾는다. 
	// 범위를 넘어서는 인덱스 접근을 막기 위해 high 값에 상한을 둔다.
	while(low <= high && high < primes.size()-1){ 
		if (sum >= n) {
			if (sum == n) cnt++;
			sum -= primes[low++];
		}
		else if (sum < n) {
			sum += primes[high++];
		}
	}

	return cnt;
}

int main() {

	// 주어진 최대값 이하에서 소수집합(primes)을 만든다. 
	for (int i = 2; i <= 4000000; i++) {
		if (isPrime[i]) continue;
		for (int j = 2; i*j <= 4000000; j++) {
			isPrime[i*j] = true;
		}
	}

	for (int i = 2; i <= 4000000; i++) {
		if (isPrime[i]) continue;
		primes.push_back(i);
	}

	cin >> n;
	cout << solve();
	
	return 0;
}

 

👨🏻‍💻 개선된 소스 코드

🛠️ 개선한점

◾ 소수 집합 만드는 로직을 for문 한 개로 줄였다.

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

vector<int> primes;
bool isPrime[4000001] = { false };
int n;

int solve() {
	int cnt = 0, sum = 0;
	int low = 0, high = 0;

	while(low <= high && high < primes.size()-1){ 
		if (sum >= n) {
			if (sum == n) cnt++;
			sum -= primes[low++];
		}
		else if (sum < n) {
			sum += primes[high++];
		}
	}

	return cnt;
}

int main() {	
 
	for (int i = 2; i <= 4000000; i++) {
		if (isPrime[i]) continue;
		primes.push_back(i);
		for (int j = 2; i*j <= 4000000; j++) {
			isPrime[i*j] = true;
		}
	}

	cin >> n;
	cout << solve();
	return 0;
}