문제
풀이
에라토스테네스의 체를 이용하여 범위 내의 소수들을 찾은 뒤, 그 소수들의 배열 중 부분배열의 합이 N이 되는 것들을 체크하면 되는 문제이다. 직접 짠 코드는 97%에서 out of bounds로 인한 문제가 생겨, Reference에서 가져온 코드를 첨부한다.
소스 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;
#define MAX 4000000
int N, sum;
int check[MAX+1]; // 0을 소수로 표기
vector<int> p_sum;
vector<int> prime_num;
int main()
{
cin >> N;
p_sum.push_back(0);
// 에라토스테네스의 체
for(int i = 2; i < sqrt(MAX); i++)
{
for(int j = 2*i; j <= MAX; j += i)
check[j] = 1; // 소수가 아님을 표시
}
for(int i = 2; i <= MAX; i++)
{
if(check[i] == 0)
{
sum += i;
p_sum.push_back(sum);
}
}
// 투포인터
int ans, left, right;
ans = 0;
left = 0;
right = 0;
while(left <= right && right < p_sum.size())
{
if(p_sum[right] - p_sum[left] > N)
{
left++;
}
else if(p_sum[right] - p_sum[left] < N)
{
right++;
}
else // (p_sum[right] - p_sum[left] == N)
{
ans++;
right++;
}
}
cout << ans;
}
//https://cocoon1787.tistory.com/357
Out of bounds 오류 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <iostream>
#include <vector>
#define MAX 4000000
using namespace std;
vector<int> prime_number;
void primenumber(int N){
bool arr[MAX+1] = {true, true, false, };
for(int i = 2; i*i<=N; i++){
if(arr[i] == false){
for(int j = 2; i*j <= N; j++){
arr[i*j] = true;
}
}
}
for(int i = 0; i<=N; i++){
if(arr[i] == false){
prime_number.push_back(i);
}
}
}
int main(){
int N;
scanf("%d", &N);
primenumber(N);
int start = 0;
int end = 0;
int sum = prime_number[0];
int cont = 0;
while(start <= end && end < prime_number.size()){
if(sum == N){
cont++;
end++;
sum += prime_number[end];
}
else if(sum < N){
end++;
sum += prime_number[end];
}
else if(sum > N){
sum -= prime_number[start];
start++;
}
}
printf("%d\n", cont);
}
