BOJ 1644 소수의 연속합/ C++

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

1644번: 소수의 연속합

백준 온라인저지 1644번 소수의 연속합 문제입니다.

 

아이디어

n이하의 소수들을 합하여 n이 될 수 있는 모든 경우의 수를 찾는 문제입니다.

n이하의 모든 소수를 에라토스테네스의 체를 이용하여 구해주고, 투포인터 알고리즘을 사용하여 크기 순서대로 놓여진 소수들을 앞에서 부터 더하여 크기가 n보다 작을경우는 다음 소수를 하나씩 더 더하고, n보다 클 경우는 가장 오래전에 더했던 소수들을 빼서 합이 n인 케이스를 모두 찾아냈습니다.

 

#include<iostream>
#include<vector>

using namespace std;

int n;
vector<int> checkPrime;
vector<int> prime;
void input() {
	cin >> n;
	checkPrime.resize(n + 1,1);
}

//에라토스테네스의 체
void findPrime(int num) {
	for (int i = 2; i*i <= n; i++) {
		if (checkPrime[i] == 0) continue;
		for (int j = i + i; j <= n; j += i) {
			checkPrime[j] = 0;
		}
	}
	for (int i = 2; i <= n; i++) {
		if (checkPrime[i]) 
			prime.push_back(i);
	}
}

void solution() {
	findPrime(n);
	int start = 0;
	int end = 0;
	int sum = 0;
	int cnt = 0;
	//투포인트
	while (1) {
		//n보다 작다면 startPoint 증가
		if (sum > n) {
			sum -= prime[start];
			start++;
			continue;
		}
		// n보다 크다면 endPoint 증가
		if (sum < n) {
			if (end >= prime.size()) break;
			sum += prime[end];
			end++;
			continue;
		}
		//n과 같다면 카운팅
		cnt++;
		if (end >= prime.size()) break;
		sum += prime[end];
		end++;
	}
	cout << cnt;
}

int main(void) {
	input();
	solution();
}