취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 26090번 문제인 완전한 수열이다.
문제는 아래 링크를 확인하자.

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

길이 $N$의 수열에는 $N(N-1)/2$가지 연속 부분 수열이 존재한다. 또한 각 연속 부분 수열에 포함되는 수의 합은 prefix sum을 전처리해두는 것으로 매번 $O(1)$에 계산할 수 있다.

따라서 이 문제는 주어진 수열의 모든 연속 부분 수열을 살펴보며 해당 부분 수열의 길이가 소수인지, 그리고 그 합이 소수인지를 판정해 조건을 만족하는 수열의 수를 세는 것으로 해결할 수 있다. 이 때, 나올 수 있는 합의 최댓값인 100만 이하의 모든 수를 에라토스테네스의 체 등으로 먼저 전처리해두면 위 과정을 빠르게 진행할 수 있다.

아래는 제출한 소스코드이다.

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

int N;
vector<int> P;
bool sieve[1000001];
void sieveinit() {
	sieve[0] = sieve[1] = 1;
	for (int i = 2; i * i < 1000001; i++) {
		if (sieve[i]) continue;
		for (int j = i * i; j < 1000001; j += i) sieve[j] = 1;
	}
	for (int i = 2; i <= N; i++) {
		if (sieve[i]) continue;
		P.emplace_back(i);
	}
}

int A[501];
int ans;

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


	cin >> N;
	sieveinit();
	for (int i = 1; i <= N; i++) {
		cin >> A[i];
		A[i] += A[i - 1];
	}

	for (auto &p : P) {
		for (int i = p; i <= N; i++) {
			if (!sieve[A[i] - A[i - p]]) ans++;
		}
	}

	cout << ans;
}