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
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;
}
'아카이빙 > BOJ' 카테고리의 다른 글
백준 3190번 - 뱀 (0) | 2019.06.18 |
---|---|
백준 11778번 - 피보나치 수와 최대공약수 (0) | 2018.10.21 |
백준 2143번 - 두 배열의 합 (0) | 2018.10.21 |
백준 15789번 - CTP 왕국은 한솔 왕국을 이길 수 있을까? (0) | 2018.06.04 |
백준 14728번 - 벼락치기 (0) | 2017.09.26 |