📖 백준 1644번 : https://www.acmicpc.net/problem/1644
조건
| 시간 제한 | 메모리 제한 |
|---|---|
| 2 초 | 128 MB |
문제
하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수들이 있다. 몇 가지 자연수의 예를 들어 보면 다음과 같다.
- 3 : 3 (한 가지)
- 41 : 2+3+5+7+11+13 = 11+13+17 = 41 (세 가지)
- 53 : 5+7+11+13+17 = 53 (두 가지)
하지만 연속된 소수의 합으로 나타낼 수 없는 자연수들도 있는데, 20이 그 예이다. 7+13을 계산하면 20이 되기는 하나 7과 13이 연속이 아니기에 적합한 표현이 아니다. 또한 한 소수는 반드시 한 번만 덧셈에 사용될 수 있기 때문에, 3+5+5+7과 같은 표현도 적합하지 않다.
자연수가 주어졌을 때, 이 자연수를 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000)
출력
첫째 줄에 자연수 N을 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 출력한다.
풀이
소수 판정을 빠르게 하는 에라토스테네스의 체 알고리즘을 활용해야 시간 제한을 맞출 수 있다. 입력값이 최대 4,000,000이 주어지기 때문에 단순하게 소수를 판정하는 방법 O(N^2)은 당연히 안되고, 제곱근까지 나눠지는 수가 있는지 판단하는 방법 O(N√N))도 느리다. O(Nlog(logN))의 복잡도를 가지는 에라토스테네스의 체 알고리즘을 사용해서 소수를 판별하는 것이 첫번째이다.
연속하는 소수의 합으로 주어진 수를 나타내는 경우의 수를 샐 때, 단순하게 접근해선 안된다. 최악의 경우 N이 4,000,000으로 주어진다. 이 때, 소수의 개수가 200,000개가 넘어가므로 O(N^2)으로 접근하면 시간 초과를 받는다. 따라서 나는 구간합과 투 포인터를 활용해서 연속하는 소수의 합을 계산했다.
소수를 판별하면서 각각의 소수들을 구간합의 형태로 저장했다. 이 후에 투 포인터를 활용하면 연속하는 소수의 구간합을 O(N)으로 구할 수 있다. i ~ j 구간합이 n보다 작을경우 j를 키워서 구간합을 높이고 n보다 클 경우 i를 키워서 구간합을 줄인다. 연속하는 소수의 합이 N과 같을 때를 체크하고 그 수를 출력하면 끝이다.
코드
#include <iostream>
#include <vector>
using namespace std;
bool isNotPrime[4000001];
vector<int> prime_number;
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int n;
cin >> n;
int k = 0;
prime_number.push_back(0);
for (int i = 2; i <= n; i++) {//에라토스테네스의 체
if (!isNotPrime[i]) {
prime_number.push_back(i + prime_number[k]);//소수를 구간합의 형태로 저장
k++;
for (int j = i * 2; j <= n; j += i)
isNotPrime[j] = true;
}
}
int cnt = 0;
for (int i = 0, j = 1; j < prime_number.size();) {//투 포인터 활용
int sum = prime_number[j] - prime_number[i];//연속하는 소수의 합
if (sum == n) {
cnt++;
++i; ++j;
}
//i ~ j까지의 연속하는 소수의 합이 n보다 작으면 j를 키워 sum값을 늘리고 n보다 클 경우 i를 키워 sum값을 줄인다.
sum < n ? ++j : ++i;
}
cout << cnt;
return 0;
}