1644 - 소수의 연속합

문제

코드

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
int n;
ll ret, sum;
vector<int> v;
int a[4000000];

void num(int n){
	for(int i = 2; i <= n; i++){
		a[i] = 1;
	}
	
	for(int i = 2; i <= n; i++){
		for(int j = 2; j*i <= n; j++){
			a[i*j] = 0;
		}
	}
	
	for(int i = 2; i <= n; i++){
		if(a[i] == 1) v.push_back(i);
	}
}

int main(){
	cin >> n;
	if(n==1) {
	cout << 0 <<'\n' ;
	return 0;
	}
	num(n);
	
	int lo = 0;
	int hi = 0;
	
	while(1){
		if(sum >= n) sum -= v[lo++];
		else if(hi > v.size()) break;
		else sum += v[hi++];
		if(sum == n) ret++;
	}
	
	cout << ret << '\n';
	
}

풀이

소수를 구하는 법은 에라토스테네스의 체를 이용했다.
--> 이건 필요한 수만큼 배열에 쭉 소수라(1이라) 입력해두고 처음부터 2부터 하나씩 차근차근 곱해나간다. 두 수를 곱해서 입력 값보다 작을 때까지만 그러면 소수가 아니니까 배열을 0으로 만든다. 배열에서 1인 경우는 소수니까 vector에 담는다.
다음은 메인에서는 투 포인터를 사용했다.
연속적인 합인데 4백만이 최대 입력 값이라 이중 for문으로 했더니 시간 초과가 나왔기 때문이다.
긴 배열에서 시작점을 처음으로 두고 lo, hi가 움직인다.
두 포인터가 가리키는 값의 합이 구해야하는 값보다 작으면 hi를 더하고 올려주고
합이 구해야하는 값보다 크거나 같으면 lo를 빼주고 lo++을 해준다.
그러면 연속적인 값의 합에 대해 나타내면서 for문이 한 번 돌 때 값을 구할 수 있게 되는 것이다.
구하려는 값과 같으면 ret++하고 이를 출력하면 된다.
계속 Out Of Bounds가 떴는데 이게 1일 때를 생각안해줘서 그랬다.
1은 소수가 아니라서 빼고 시작했는데 입력 값이 1부터라 생각해줘야 하는 것을 잊고 있었다.

결과

후기

그리디라는 알고리즘이 진짜 어렵다는 것을 느꼈다.
규칙성은 딱히 없고 구현 같으면서도 규칙이 있는듯 하기도 하고
그냥 노력으로 커버해야하는 부분 같다..