아카이빙/BOJ

백준 1644번 - 소수의 연속합

셩님 2018. 10. 21. 18:35

백준 1644번 - 소수의 연속합

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


문제

  • 2 이상의 자연수가 주어졌을 때,

  • 이 자연수를 하나 이상의 연속된 소수의 합으로 나타낼 수 있는 경우의 수

  • 예를 들어,

    • 41 : 2+3+5+7+11+13 = 11+13+17 = 41 (세 가지)


입력

  • 자연수 N (1 ≤ N ≤ 4,000,000) 


출력

  • 경우의 수


접근

  • 에라토스테네스의 체를 활용하여 n 까지의 소수를 미리 구함

  • 투 포인터를 활용하여 포인터 2개 사이의 구간합을 구해가며 n가 같음을 확인

    • 구간합이 n보다 작으면 우측의 포인터를 증가

    • 구간합이 n보다 크거나 같으면 좌측의 포인터를 증가

    • 우측의 포인터가 끝에 도달하면 종료

C++ Code

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

int n;
vector<int> primes;
vector<bool> check;

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

cin >> n;
//에라토스테네스의 체
check.resize(n + 1, true);
for (int i = 2; i*i <= n; i++)
{
if (!check[i]) continue;
for (int j = i * i; j <= n; j += i)
{
check[j] = false;
}
}

for (int i = 2; i <= n; i++)
{
if (check[i]) primes.push_back(i);
}

//투포인터를 이용
//1. lo와 hi 사이의 구간합을 구한다.
//2. 구간합이 n보다 크거나 같으면 가장 왼쪽의 수를 뺀다.
//3. 구간합이 n보다 작으면 가장 오른쪽의 수를 더한다.
int result = 0, sum = 0, lo = 0, hi = 0;
while (1) {
if (sum >= n) {
sum -= primes[lo++];
} else if (hi == primes.size()) {
break;
} else {
sum += primes[hi++];
}

if (sum == n) result++;
}

cout << result;

return 0;
}