[백준/C++] #1644 소수의 연속합 (Two Pointer)

문제

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

 

구상

"연속된" 소수의 합으로 나타낼 수 있는 경우를 구하라길래 바로 two pointer를 사용한 prefix sum 형태의 배열이 떠올랐다. 그러면 소수로 이루어진 배열이 필요한데, 어떻게 소수를 판별해서 소수로만 이루어진 배열을 만들까? 라는 생각이 들었다. 실제로 해당 부분을  오랜 시간 고민했고, 가장 구현이 빡셌다. 소수 판별은 N까지만 되면 되었고, 4부터 판별 시작하면 되었다. 4부터 해당 수에 대한 배수들을 구해서 false로 판별하면 되겠다는 생각이 들었다. 배수는 2의 배수부터 sqrt(N)의 배수까지 확인하면 되었고, 배수라는게 겹치는 건 생각안해도 되기에 제곱수부터 고려하면 되었다. 

 

표로 설명하는게 이해하기 쉬워서 표로 설명하겠다. N은 50이라 가정하겠다. 

i는 아래와 같이 2부터 1씩 순차 증가하고, j는 i*i부터 i씩 순차 증가한다. 

i	j	j += i
2	2^2 = 4	6	8	10	12	14	16	18	20
3	3^3 = 9	12	15	18	21	24	27	30	33
4	4^4 = 16	20	24	28	32	36	40	44	48
5	5^5 = 25	30	35	40	45	50
6	6^6 = 36	42	48
7	7^7 = 49

 

이런 과정을 거치면 보다 효율적으로 모든 배수를 걸러낼 수 있다. 

 

그리고, 투 포인터를 사용할 때는 깔끔하게 나올 수 있는 경우를 나누는게 정말 중요하고, 인덱스가 배열 범위 밖으로 넘어가지 않도록 해야함을 다시금 느낄 수 있었다. 기본 과정은 작거나 같으면 키우고(인덱스 주의), 크면 작게하는 것임을 잊지 말자. 같을때만 추가로 처리해주면 된다. 

 

알고리즘

: two pointer, 에라토스테네스의 체

 

풀이 + 코드

1. 에라토스테네스의 체 사용하여 소수 판별 
2. 소수로 이루어진 배열 만들기
3. sum 구하며 two pointer로 구간 설정 -> 소수의 합 경우의 수 계산

  => 따로 prefix sum 구할 필요가 없음!

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#define MAX 4000001
#define INF 987654321
#define endl "\n"
using namespace std;
/*
1644 소스의 연속합
resize, memset, fill, assign 차이.. 확실히 알아두자
*/

int N;
vector<bool> is_prime; // 소수 판별
vector<int> prime; // 소수 배열 -> prefix sum
int res = 0; // 경우의 수

void generate_primes() {

    is_prime.assign(N +1, true); // 인덱스 N까지 있도록 초기화
    is_prime[0] = is_prime[1] = false;

    // 소수 판별
    for (int i = 2; i * i <= N; i++) { // 순차적으로 증가
        if (is_prime[i]) {
            for (int j = i * i; j <= N; j += i) { // 4부터 시작
                is_prime[j] = false; // N까지 배수들은 전부 false로 설정
            }
        }
    }

    // prime 배열 만들기
    for (int i = 2; i <= N; i++) {
        if (is_prime[i]) {
            prime.push_back(i);
        }
    }
}

void solution() {
    // 소수 판별, 배열 생성
    generate_primes();

    // 투 포인터로 구간 설정하며 소수의 합 경우의 수 계산
    int s = 0; int e = 0; int sum = 0;
    while (true) {
        if (sum >= N) sum -= prime[s++]; // 크면 감소하도록 하고, 
        else if (e == prime.size()) break; // 작다면 미리 경계 이상 커지지 못하도록 제한 걸고 
        else sum += prime[e++]; // 제한에서 안 걸린 경우에는 증가하도록 한다. 

        if (sum == N) res++;
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    // 입력
    cin >> N;

    // 로직
    solution();

    // 출력
    cout << res;

    return 0;

}