[PS스터디 심화반] 3주차 백준 소수의 연속합

개요

 

소수를 이용하며 연속적인 합을 구하는 문제입니다.

 

https://www.acmicpc.net/problem/1644

1644번: 소수의 연속합

 

리뷰와 피드백

 

이번 문제에서는 소수를 구하는 부분과 연속적인 합을 구하는 부분 두 가지로 나눌 수 있었습니다.

먼저 처음 소수를 구하는 부분에서의 방법이 두 가지로 나눠졌었는데, 루트N의 시간복잡도로 각 소수들을 구하려하니

주어진 시간 제한 안에 들어올꺼란 확신이 들지 않았습니다. 그래서 에라스토테네스의 체를 이용해 NlglgN의 시간복잡도에 소수들을 구하였습니다. ( 전자의 방식으로도 통과되었습니다. 하지만 후자가 훨씬 빨랐네요 )

 

이후 각 소수들의 연속적인 합을 구하기 위해 저는 단순히 유효한 범위를 주고 단순 반복으로 합을 구하였습니다.

 

 

 

개선안

 

 

앞서 말씀드린 듯,  유효범위안을 단순 반복하여 연속합을 구하였습니다. 그에 반해 다른 분들은 슬라이딩 윈도우를 통해

효율적으로 매 연속합을 구하셨습니다

슬라이딩 윈도우 방식도 많이 해보진 않아 이런 방식으로 먼저 구현해보았습니다.

이후 다른 분들이 슬라이딩 윈도우를 통해 구현한 것에 감명을 받아 저 또한 제 코드를 바꿨습니다. 

 

두 방식 사이의 시간차이는 없었습니다.

 

 

 

개선 전 / 후   코드 전문

 

... 생략
// 개선 전

#include <iostream>
#include <vector>

using namespace std;

int n;
vector<int> prime_v;

void sieve(int n) {
    vector<bool> state(n+1, true);
    state[1] = false;
    for (int i = 2; i*i <= n; i++) {
    	if (!state[i]) continue;
        for (int j = i*i; j <= n; j += i)
        	state[j] = false;
    }
    for (int i = 2; i <= n; i++) {
    	if (state[i]) prime_v.push_back(i);
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n;
    sieve(n);

    int ans = 0;
    for (int i = 0; i < prime_v.size(); ++i) {
        long long sum = 0; 
        for (int j = i; j < prime_v.size(); ++j) {
            sum += prime_v[j];
            if (sum > n) break;
            if (sum == n) ++ans;
        }
    } 

    std::cout << ans; 
}

 

 

 

... 생략
// 개선 후

#include <iostream>   // 2부터 n까지의 소수를 O(루트N) 시간복잡도 구하려했으나  
#include <vector>     // n == 4백만일 경우 시간초과의 우려가 있었습니다.
                      // 그래서 O(NlglgN)의 에라스토테네스의 체를 이용하여 소수를 구하였습니다.  
using namespace std;  /** <!오타 수정> 3번 주석의 O(Nlglgn) -> O(NlglgN) 소문자 n -> 대문자 N **/
                      // sliding window 추가. 연속적인 합을 구하며 오름차순이기에 적용 가능
int n;
vector<int> prime_v;

// 에라스토테네스의 체를 이용하여 n까지의 소수를 구하고 prime_v에 담습니다.
void sieve(int n) {
    vector<bool> state(n+1, true);
    state[1] = false;
    for (int i = 2; i*i <= n; i++) {
    	if (!state[i]) continue;  // 이미 체크된 수는 확인을 위한 반복과정 제외. 시간 획기적 단축
        for (int j = i*i; j <= n; j += i) 
        	state[j] = false;  // 소수의 배수들은 소수가 될 수 없음. 체크
    }
    for (int i = 2; i <= n; i++) {
    	if (state[i]) prime_v.push_back(i);
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n;
    sieve(n);

    int ans = 0; long long sum = 0; // sliding window로 구현하였습니다. 시간복잡도 O(2N)..?
    for (int r_idx = 0, l_idx = 0; r_idx < prime_v.size(); ++r_idx) {  
        sum += prime_v[r_idx];
        while (sum > n) { 
            sum -= prime_v[l_idx]; 
            ++l_idx; 
        }  
        if (sum == n) ++ans;  // 이번 루트에서 찾는 값을 구할 수 있다면 ans증가
    } 

    std::cout << ans; 
}

 

 

 

 

향후 방침, 느낀 점

 

 

에라스토테네스의 체를 사용할 수 있었던 경험과 슬라이딩 윈도우를 통한 연속합을 구하는 경험을 할 수 있었습니다.

재밌네요!