1644 소수의 연속합

보자마자 어떻게 풀지 감 와서 그대로 코드 옮겼다. 먼저 소수 벡터 구하고 다음으로 투포인터 사용해서 합이 n이 될 때 개수 세기. 소수는 2학년 때 과제 한다고 엄청 공부 많이 했는데 그 때 에라토스테네스 체 찾아본 적 있어서 이걸로 썼다. 내 기억상으로 이게 제일 빨랐음. 다음으로 투포인터로 합이 n인 경우 세기. 이건 할 말이 없다. 그냥 투포인터!

 

시간복잡도는 O(NlonN).. 

소수 구하는 부분이 O(NlonN)이고 투포인터는 O(N)이라 합쳐서 O(NlonN)이 된다.

 

 

 

음.. 완벽하다 생각했는데 뭐가 문제지..

이게 작은 수는 돌아가는데 큰 수에서 터진다..

 

#include <iostream>
#include <vector>
using namespace std;
using i64 = long long;
int main() {
    int n;
    scanf("%d", &n);
    vector<bool>v(n+1, true);
    vector<i64>prime;
    
    if(n == 1){
        printf("0");
        return 0;
    }
    
    for(int i = 2; i*i <= n; i++){
        if(v[i]){
            for(int j = i*i; j <= n; j+=i)
                v[j] = false;
        }
    }
    
    for(int i = 2; i <= n; i++){
        if(v[i])
            prime.push_back(i);
    }
    
    int l = 0, r = 0;
    int ans = 0;
    i64 count = prime[0];
    
    while(l < prime.size()){
        if(count<n)
            count += prime[++r];
        else if(n<count)
            count -= prime[l++];
        else{
            ans++;
            count -= prime[l++];
        }
    }
    
    printf("%d", ans);
    
    return 0;
}

 

 

처음에는 count에서 떠진다고 생각했는데 이게 n 범위를 왔다갔다 해서 안 터질 것 같은데.. 음... 게다가 long long 인디

 

 

 

---

아..!

r이 끝까지 갔는데도 count가 n보다 작으면 r++해버려서 문제가 생겼다. 

그래서 r이 끝이면 그만두게끔 조건을 달아줘야 한다.

 

투포인터.. 신기하구만..

 

 

#include <iostream>
#include <vector>
using namespace std;
using i64 = long long;
int main() {
    int n;
    scanf("%d", &n);
    vector<bool>v(n+1, true);
    vector<i64>prime;
    
    if(n == 1){
        printf("0");
        return 0;
    }
    
    for(int i = 2; i*i <= n; i++){
        if(v[i]){
            for(int j = i*i; j <= n; j+=i)
                v[j] = false;
        }
    }
    
    for(int i = 2; i <= n; i++){
        if(v[i])
            prime.push_back(i);
    }
    
    int l = 0, r = 0;
    int ans = 0;
    i64 count = prime[0];
    
    while(l < prime.size()){
        if(count<n){
            if(r == prime.size()-1)
                break;
            count += prime[++r];
        }
        else if(n<count)
            count -= prime[l++];
        else{
            ans++;
            count -= prime[l++];
        }
    }
    
    printf("%d", ans);
    
    return 0;
}