BOJ - 1644번 소수의 연속합(C++)

문제 출처: https://www.acmicpc.net/problem/1644

문제 난이도

Gold 3

문제 접근법

소수의 연속합이기 때문에 먼저 에라토스테네체의 해로 소수를 판별했다.
그리고 연속합을 가리기 위해 삼중 for문을 써서 순서대로 더해줬는데 시간초과 났다.
-> 투 포인트 알고리즘을 사용하면 된다.

통과 코드

#include <iostream>
#include <vector>
#include <algorithm>


using namespace std;


vector<int> Eratosthenes(int N){

	vector<int> prime;

	for (int i = 2; i <= N; i++) {
		bool flag = true;
		for (int j = 2; j*j <= i; j++) {
			if (i % j == 0) {
				flag = false;
				break;
			}
		}
		if (flag) prime.push_back(i);
	}
	return prime;
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int N;
	cin >> N;
	vector<int> p;
	p = Eratosthenes(N);
	int res = 0;
	if (p.empty()) {
		cout << 0;
		return 0;
	}
	int sum = p[0];
	int plusIdx = 0, minusIdx = 0;
	while (minusIdx <= plusIdx && plusIdx < p.size()) {
		if (sum < N) {
			if (++plusIdx < p.size()) sum += p[plusIdx];
		}
		else if (sum == N) {
			res++;
			if (++plusIdx < p.size()) sum += p[plusIdx];
		}
		else if (sum > N) {
			sum -= p[minusIdx++];
		}
	}

	cout << res << "\n";
	
	return 0;
}

피드백

사진에서 보다 싶이 시간초과 후에 다시 제출 했는데 런타임 에러가 났다. 그래서 자연수 범위가 너무 커서 그런가 싶어 long long 변수로 다 바꿨더니 오히려 시간 초과가 났다.
알고보니 N이 1 일 때, 에러가 나는 거였다. sum에서 p[0] 값을 박아 놓고 시작하니깐 벡터 값이 비어있을 때 처리가 안 된 것이다. 그래서 조건문을 추가하고 돌렸더니 통과.

이 문제도 자의로 푼 건 에라..테네체의 해 뿐이라 투 포인트는 다른 사람 코드를 참고했다. 분발하자!