[210714][백준/BOJ] 1644번 소수의 연속합

문제

입출력

풀이

하나 이상의 연속된 소수로 입력받은 n을 나타낼 수 있는 경우의 수를 찾는 문제이다.

• 20은 소수로 나타낼 수 없다.
• 3은 소수 3으로 나타낼 수 있다.
• 41은 2+3+5+7+11+13, 11+13+17, 41 로 나타낼 수 있다.

n이 최대 400만까지이므로 O(n) 알고리즘을 사용해야하며 1차원 배열에서 두개의 포인터를 조작하여 결과를 얻을 수 있는 투포인터 알고리즘을 사용하면 된다.
https://butter-shower.tistory.com/226

1. 소수들은 에라토스테네스의 체를 통해 구하며 vector V에 넣어준다.
2. start와 end를 나타내는 두개의 포인터 s와 e를 0으로 초기화해준다.
3. 두 포인터로 나타내는 합(e - s)이 n보다 크거나 같다면 s++를 해준다.
4. 두 포인터로 나타내는 합이 n보다 작으면 e++를 해준다.
5. 두 포인터로 나타내는 합이 n과 같다면 cnt++를 해준다. (경우의수에 해당)
6. 합이 n보다 크거나 같지 않으면서 e가 배열의 끝에 도달할때까지 반복한다.

https://m.blog.naver.com/kks227/220795165570

코드

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

bool p_list[SIZE];
vector<int> V;

// 에라토스테네스의 체로 소수 구하기
void prime()
{
	for (int i = 2; i < SIZE; ++i)
		p_list[i] = 1;

	for (int i = 2; i < SIZE; ++i) {
		if (p_list)
		{
			for (int j = 2 * i; j < SIZE; j += i)
				p_list[j] = 0;
		}
	}

	for (int i = 2; i <= SIZE; ++i)
		if (p_list[i])
			V.push_back(i);
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	prime();
	int n;
	cin >> n;

	int s = 0, e = 0, res = 0, sum = 0;

	while (true)
	{
		if (sum >= n) sum -= V[s++];
		else if (e == V.size()) break;
		else sum += V[e++];
		if (sum == n) res++;
	}
	cout << res << '\n';
}