📘 문제

문제링크 : https://www.acmicpc.net/problem/1644 (단계별로 풀어보기 : 투 포인터)

📝 문제 풀이

해당 문제는 투 포인터를 활용한다.
그런데 문제를 풀기 위해서는 일단 소수를 구하는 알고리즘을 알아야한다. 소수는 1과 자기자신으로만 나눠지는 수로 2, 3, 5, 7, 9 ... 등이 있는데, 주어진 N까지의 소수를 모두 구해야한다. 만약 이중 포문으로 소수를 구하면 N은 최대 4,000,000 이므로 소수를 구하는 것으로만 시간초과가 날 것이다. 따라서 해당 문제에서 소수를 구할때는 에라토스테네스의 체 알고리즘을 사용하여 소수를 구해야한다. 에라토스테네스의 체란? 0,1은 버려두고 2부터 삭제되지 않은 수(즉 소수)의 배수들(자기 자신 제외)을 모두 지우는 과정을 원하는 범위의 수까지 반복하여 소수를 구하는 방식이다.
만약 10까지의 소수를 구한다면?

2, 3, 4, 5, 6, 7, 8, 9, 10
-> 2의 배수 삭제
2, 3, 4, 5, 6, 7, 8, 9, 10
-> 3의 배수 삭제
2, 3, 4, 5, 6, 7, 8, 9, 10
-> 5의 배수 삭제
2, 3, 4, 5, 6, 7, 8, 9, 10
-> 7의 배수 삭제
2, 3, 4, 5, 6, 7, 8, 9, 10

이런 과정을 거쳐 남은 2, 3, 5, 7 이 소수가 되는 것이다.

이 알고리즘으로 주어진 N까지의 소수를 구한다.
그 이후 투 포인터를 사용해서 연속한 값들을 더했을 때 N이 되는 경우의 수를 구한다.
그럼 왼쪽 포인터가 한 인덱스마다 오른쪽 포인터가 왼쪽 포인터 위치부터 소수가 들어있는 배열의 마지막 인덱스까지 탐색하여 합이 N과 같은지를 봐주면 된다.
필자는 처음 이러한 방식으로 문제를 풀었다.
그런데 생각보다 걸린시간이 많이 나와 코드를 최적화 하기위해 검색해보고 최적화 방법을 찾았다.
소수를 구해서 배열에 넣어줄때 소수 숫자 자체를 넣는 것이 아니라 누적합을 사용했다.
누적합을 저장해서 투포인터를 사용해서 조건을 탐색할 때 구간 합을 이용해서 조건을 검색하는 방식이다.
처음 코드가 소스코드1 이고 최적화한 코드가 소스코드2 이다.
제출하여 보니 시간이 많이 줄은 것을 확인할 수 있었다.

✏️ 알고리즘 스케치

💻 소스코드

소스코드 1
#include <iostream>
#include <vector>
using namespace std;

vector<int> makePrimeNumbers(bool* arr, int N);
void findSolution(vector<int> vecArr, int N);

int main()
{
    int N;
    cin >> N;

    bool *arr;
    arr = new bool[N+1];

    vector<int> vecArr = makePrimeNumbers(arr, N);
    findSolution(vecArr,N);

    return 0;
}

vector<int> makePrimeNumbers(bool* arr, int N)
{
    fill(arr,arr+N+1,true);

    arr[0] = arr[1] = false;
    for(int i=2; i*i<=N; i++){
        for(int j=i*i; j<=N; j+=i){
            arr[j] = false;
        }
    }

    vector<int> vecArr;
    for(int i=2; i<=N; i++){
        if(arr[i]==true)
            vecArr.push_back(i);
    }

    delete[] arr;
    return vecArr;
}

void findSolution(vector<int> vecArr, int N)
{
    int ptr1, ptr2, sum, sol=0;
    int size = vecArr.size();

    for(ptr1 = 0; ptr1<size; ptr1++){
        ptr2 = ptr1;
        while(ptr2<size){
            sum = 0;
            for(int i = ptr1; i<=ptr2; i++)
                sum += vecArr[i];
            if(sum > N)
                break;
            else if(sum == N)
                sol++;
            ptr2++;
        }
    }

    cout << sol << endl;
}

소스코드2
#include <iostream>
#include <vector>
using namespace std;

vector<int> makePrimeNumbers(bool* arr, int N);
void findSolution(vector<int> vecArr, int N);

int main()
{
    int N;
    cin >> N;

    bool *arr;
    arr = new bool[N+1];

    vector<int> vecArr = makePrimeNumbers(arr, N);
    findSolution(vecArr,N);

    return 0;
}

vector<int> makePrimeNumbers(bool* arr, int N)
{
    fill(arr,arr+N+1,true);

    arr[0] = arr[1] = false;
    for(int i=2; i*i<=N; i++){
        for(int j=i*i; j<=N; j+=i){
            arr[j] = false;
        }
    }

    vector<int> vecArr;
    vecArr.push_back(0);

    int sum = 0;
    for(int i=2; i<=N; i++){
        if(arr[i]==true){
            sum += i;	// 누적합을 구해서 넣어주기
            vecArr.push_back(sum);	
        }
    }

    delete[] arr;
    return vecArr;
}

void findSolution(vector<int> vecArr, int N)
{
    int ptr1=0, ptr2=0, sol=0;
    int size = vecArr.size();

    while(ptr1<=ptr2 && ptr2<size){ 
        if(vecArr[ptr2]-vecArr[ptr1]>N)	// 구간합을 이용해서 탐색
            ptr1++;
        else if(vecArr[ptr2]-vecArr[ptr1]<N)
            ptr2++;
        else{
            sol++;
            ptr2++;
        }
    }

    cout << sol << endl;
}