백준 1644

문제

하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수들이 있다. 몇 가지 자연수의 예를 들어 보면 다음과 같다.

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을 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 출력한다.

풀이

N이 4000000까지라 N까지의 모든 소수를 vector에 넣을 수 있다.

그러므로 4000000까지의 모든 소수를 구해 vector에 넣어주고, 그 값들을 이용해 구간합 알고리즘을 위한 배열을 하나 만들어준다.

전체 구간내의 특정한 구간(합이 N이되는 구간)을 전부 구해야 하기 때문에 투포인터를 이용해주어야 한다.

left와 right pointer를 둘다 소수vector의 초항으로 잡아주고,
sum[right] - sum[left]가 N보다 크면 left += 1
sum[right] - sum[left]가 N보다 작으면 right += 1
sum[right] - sum[left]가 N이면 정답을 가리키는 변수에 +1해주고, right += 1을 해주면 된다.

소수 구하기

나는 이 문제에서 4000000까지의 소수를 구하기 위해

bool isprime(int a){
    for(int i=2; i*i<=a; i++){
        if(a%i == 0)
            return false;
    }
    return true;
}

sqrt(N)까지를 비교해주는 방식을 썼다.

이것보다는 에라토스테네스의 채 방식을 써주는 것이 좋다.
2~N까지의 모든 정수를 토대로, 그 정수의 배수를 체크해주는 방식이다.
에라토스테네스의 채는 거의 선형시간에 유사한 시간이 걸리므로, 위의 내가 기술한 방식보다 훨씬 시간이 덜걸린다.

정답 코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int N, sum_arr[1000001], ans;
vector<int>prime;
bool isprime(int a){
    for(int i=2; i*i<=a; i++){
        if(a%i == 0)
            return false;
    }
    return true;
}
// void dfs(int st, int dest){
//     if(dest > prime.size()) return;
//     if(prime[dest-1] > N) return;
//     if(sum_arr[dest] - sum_arr[st-1] == N){
//         ans += 1;
//         dfs(st, dest+1);
//         return;
//     }
//     if(sum_arr[dest] - sum_arr[st-1] > N){
//         dfs(st+1, dest);
//     }else if(sum_arr[dest] - sum_arr[st-1] < N){
//         dfs(st, dest+1);
//     }
// }
int main(){
    cin>>N;
    for(int i=2; i<=4000000; i++){
        if(isprime(i))
            prime.push_back(i);
    }
    for(int i=1; i<=prime.size(); i++){
        sum_arr[i] = sum_arr[i-1] + prime[i-1];
    }
    // dfs(1,1);
    int left=1, right = 1;
    while(left <= right && right <= prime.size()){
        if(sum_arr[right] - sum_arr[left-1] >N)
            left += 1;
        else if(sum_arr[right] - sum_arr[left-1] < N)
            right += 1;
        else{
            ans += 1;
            right += 1;
        }
    }
    cout<<ans;
}

dfs, while둘다 똑같다.