I. 문제 소개
[문제링크](https://www.acmicpc.net/problem/1644)
[1,4000000] 범위의 자연수가 주어질 때, 해당 자연수를 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 구하는 문제이다.
II. 접근 방법
1. 일단 브루트 포스
소수의 집합을 P = {2, 3, 5, ...} 라고 할 때, Brute Force로 문제를 해결하는 의사코드는 아래와 같다.
for i = 0; P[i] <= N; ++i
Subset_sum = P[i]
for j = i + 1; subset_sum <= N; ++j
if Subset_sum == N:
Answer = Answer + 1
Subset_sum = Subset_sum + P[j]자연수 N 보다 작은거나 같은 수로만 이루어진 집합 P의 길이를 L 이라고 하면, O(L^2) 의 시간 복잡도를 가지는데, N의 최대값이 4000000 이고, [2,4000000] 범위 내에 있는 소수의 개수는 283147개 이므로 제한시간 2초안에 수행할 수 없음을 알 수 있다.
2. 규칙 찾아보기
위의 Brute Force 코드는 집합 P의 매 시작점 마다 새로운 연속합을 만들어내어 매우 비효율적임을 알 수 있다.
이 문제에서 주목해야할 점은 바로 '연속합' 이라는 점과 P가 오름차순이라는 점이다.
연속합을 구성하는 P 에 대한 부분집합을 S 라고 하고, S 의 첫 원소와 마지막 원소의 P에 대한 index 값을 각각 beg, end라고 하자.
초기조건 : beg = end = 0, 즉, S = {P[0]}, Ans = 0
1. S의 원소들의 합과 N 의 값을 비교하여 아래 3가지 중 조건에 맞는 한가지 동작을 수행한다.
(1) 합이 N 보다 작으면, end를 1 증가시켜 집합 S를 확장시킨다.
(2) 합이 N 보다 크면, beg를 1 증가시켜 집합 S를 축소시킨다.
(3) 합이 N 과 같다면, Ans를 1 증가시키고, end를 1 증가시켜 집합 S를 확장시킨다.
2. 만약 P[end] 의 값이 N 보다 작거나 같다면, 시행 1 로 돌아간다.
여기서 동작 1 - (1)과 1 - (2)을 반대로 했을때를 가정하여 해당 동작에 대한 타당성을 증명해보자.
만약 1 - (1) 에서 집합 S를 확장시키기 위해 beg를 1 감소시킨다고 가정해보자.
beg-1 에서 beg로 증가시킨 시행을 보면, S의 범위가 [beg-1, end'] (end' <= end)일 떄, S의 연속합이 N을 초과하기에 beg를 1 증가시켜 S를 축소시킨 것이다.
그런데, S의 범위가 [beg,end] 인 상황에서 그 합이 N보다 작아 beg를 감소시킨다면, [beg-1, end'] 때의 상황보다 더 많거나 같은 원소를 포함하게 될텐데, 그 때의 연속합은 N 보다 커지는 것이 자명하기에 S를 확장시킬 때, beg를 감소시킬 필요가 없는 것이다.
(1-(2) 의 경우도 이같은 이유와 동일하다.)
이러한 과정을 시각화 하면 애벌레가 꿈틀대며 앞으로 나아가는 모습처럼 보이는데,
집합 P를 기준하여 애벌레가 몸의 길이를 확장/축소하며 이 애벌레의 몸통이 가로지르는 집합 P와 평행한 영역 역시 확장/축소 하므로 해당 영역을 부분집합 S라 보아 연속합을 N과 비교하는 것 같은 모습이다.
이 과정을 코드로 나타내 보면 아래와 같다.
while(beg <= end && end <= val)
{
if(sum > val)
{
sum -= beg;
beg = nextPrimeNum(beg, arr);
}
else
{
if(sum == val) result++;
end = nextPrimeNum(end, arr);
sum += end;
}
}III. 전체 코드
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
void makePrime(vector<bool> &arr)
{
int val = (int)arr.size();
arr[1] = false;
for(int i = 2; i <= sqrt(val); ++i)
{
if(arr[i])
for(int j = i * 2; j <= val; j += i)
arr[j] = false;
}
}
int nextPrimeNum(int pointer, const vector<bool> &arr)
{
int n = pointer;
int val = (int)arr.size();
while(n <= val && !arr[++n]);
return n;
}
int main(void)
{
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int val;
vector<bool> arr;
cin>>val;
arr.assign(val + 1, true);
makePrime(arr);
int beg = 2, end = 2;
int sum = 2;
int result = 0;
while(beg <= end && end <= val)
{
if(sum > val)
{
sum -= beg;
beg = nextPrimeNum(beg, arr);
}
else
{
if(sum == val) result++;
end = nextPrimeNum(end, arr);
sum += end;
}
}
cout<<result;
return 0;
}IV. 제출결과
V. 후기
sum 과 N의 대소비교를 통해 부분집합의 범위를 조절해가는 것이 마치 이분탐색을 하는 듯한 느낌이 들었다.
또한, 직관적으로 위와 같은 방식으로 문제가 해결될 것 같다는 느낌을 받는건 쉬웠지만, 이것의 타당성을 증명하는 것은 그보다 조금 더 어려웠던 것 같다.
하지만, 이렇게 내가 할 수 있는 수준에서 어떠한 타당성을 증명하는 과정이 알고리즘 문제 해결을 더 즐겁게 해줌을 느낄 수 있었다.
