[백준] 1644번 소수의 연속합
[백준] 1644번 소수의 연속합
문제 링크: https://www.acmicpc.net/problem/1644
문제 및 입출력
문제 접근
연속합이므로, 두 포인터로 구할 수 있는 문제이다.
2부터 입력받은 수까지의 소수들을 에라토스테네스의 체를 사용하여 구한다.
해당 소수들을 vector에 넣는다.
구간의 앞 뒤를 가르키는 두 개의 포인터를 만든다.
두 포인터가 처음에는 맨앞을 가르킨다.
구간의 합이 target보다 작다면, end pointer를 +1 해주고, sum에 더한다.
구간의 합이 target보다 크거나 같다면, sum에서 start가 가르키는 수를 빼주고, start를 +1 해준다. 만약 sum과 target이 같다면 result를 +1해준다.
소수가 아예 없을 경우의 수를 생각하지 못해, outofbounds 런타임 에러가 계속 나타났다.
코드 구현(c++)
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
bool num[4000001];
vector <int> v;// 소수 넣는 vector
int target;
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin >> target;
memset(num, false, sizeof(num));
for(int i = 2 ; i <= target ; i++){
for(int j = i*2 ; j <= target ; j = j+i){
num[j] = true;
}
}
for(int i = 2 ; i <= target ; i++){
if(!num[i]) v.push_back(i);
}
int start = 0;
int end = 0;
int result = 0;
int maxSize = v.size();
if(maxSize != 0){
int sum = v[start];
while(end <= maxSize && start <= end){
if(sum >= target){
if(sum == target) result++;
sum -= v[start];
start++;
}
else{
end++;
//if(end > maxSize) break;
sum += v[end];
}
}
}
cout << result << "\n";
}
Author And Source
이 문제에 관하여([백준] 1644번 소수의 연속합), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@kpg0518/백준-1644번-소수의-연속합저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)