백준 1644번, 소수의 연속합 풀이

문제

백준 1644번

풀이

에라토스테네스 체를 사용하여 구간 $[2, N]$ 사이의 모든 소수를 구해줍니다.

구한 소수를 배열에 오름차순으로 두고, 그 배열의 길이를 $ K $로 둡니다.

 

어떤 구간이 $ N $이 되는지 찾아봅시다.

 

첫번째로는 누적합을 사용하여 모든 $ i, j (1 \leq i \leq j \leq N) $에 방문하여 $ psum[j] - psum[i] = N$인지 확인해주면 $ O(K^2) $에 가능합니다.

 

하지만, $ N $의 범위가 $ 4,000,000 $이므로 $ K $가 $ 10,000 $을 넘어가서 제곱 풀이는 사용할 수 없습니다.

 

 

누적합에서는 모든 $i, j$를 방문하지만, 투포인터로 가능한 $i, j$만 빠르게 탐색할 수 있습니다.

투포인터의 왼쪽 포인터를 $ L $, 오른쪽 포인터를 $ R $이라고 두고, 구간 $ [L, R] $의 합을 $sum$이라고 둡니다.

 

매번,

$ sum \leq N $이면, $ sum $에 $ prime[R] $을 더해주고, $ R $을 1 증가시킵니다.

그렇지 않다면, $ sum $에 $ prime[L] $을 빼주고, $ L $을 1 증가시킵니다.

 

최악의 경우, $ L, R $이 모두 $ 1...K $를 방문하므로 기존의 시간복잡도(누적합 완탐) $ O(K^2) $에서 $ O(2K) $로 줄일 수 있고, 상수가 무시할만한 수준이므로 복잡도는 $ O(K) $가 됩니다.

소스코드

#include <bits/stdc++.h>

#define all(v) v.begin(), v.end()

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair <ll, ll> pll;
typedef vector<int> vi;
typedef vector <ll> vl;

vi vis(4000001);

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	vi prime;

	int n; cin >> n;
	int k = n;
	for (int i = 2; i <= k; i++) {
		if (!vis[i]) prime.push_back(i);
		for (int j = i; j <= k; j += i) vis[j] = 1;
	}

	if (!prime.size()) {
		cout << "0";
		return 0;
	}

	int l = 0, r = 1, sum = prime[0], ans = 0;
	for (; l < prime.size(); ) {
		if (n == sum) ans++;
		if (n <= sum) {
			sum -= prime[l++];
		} else {
			if (r < prime.size()) sum += prime[r++];
			else break;
		}
	}

	cout << ans;
}