백준 1644 소수의 연속합

소수들의 연속합을 구하는 문제이다. 어떤 수를 입력으로 받아, 그 수를 소수의 연속합으로 어떻게 표현할 수 있는지 개수를 출력해주면 된다. 문제 제목이 너무 문제 내용이다...

일단 소수의 리스트를 가지고 있어야 하므로, 에라토스테네스의 체를 사용해 N의 최대범위 안의 모든 소수를 구한다.

소수의 리스트를 완성한 후, 투 포인터 알고리즘을 사용해 연속합을 구해가며 자연수 N을 찾는다.

소수가 들어있는 배열이 있고, 그 배열의 원소를 가르키는 Right(R) 인덱스와, Left(L) 인덱스를 만든다. 두 인덱스는 첫번째 원소를 가르킨다. 여기에, 현재 합을 저장하는 sum 변수를 만들어 주면 연산할 준비가 되었다.

만약, sum이 우리가 찾는 N 보다 작으면 R을 한칸 증가시킨다.

R을 증가시키고, R이 가르키는 원소를 sum에 더한다. 이 과정을 sum이 N과 같거나 클때까지 반복한다.

만약 N = 41 이라 가정하면,  2 + 3 + 5 + 7 + 11 = 41이다. 우리가 찾는 조합이 완성되었다. 이제 조합의 개수를 한개 증가시키고 다음으로 넘어가야 한다. 이 상황에서 R을 한칸 증가시키는 것은 의미가 없다. 무조건 N보다 커지므로 우리는 이제 L을 한칸 증가시킨다.

그러면 sum = 39가 되고, 다시 N보다 작아지게 된다. 여기서 R을 또 증가시킨다.

3 + 5 + 7 + 11 + 13 = 41이다. 또 조합의 수를 늘려주고, L을 증가시켜 같은 연산을 반복한다. 이 반복의 종료조건은, L이 N 보다 커질때다. L이 N 과 같을때는 원소 개수를 한개로 볼 수 있지만, 그것보다 커지면 아무 의미없는 연산이 되므로 해당 조건으로 루프를 돌리게 된다.

---

#include <iostream>
#include <string.h>

bool primeFilter[4000001];

int main()
{
    memset(primeFilter, 1, sizeof(primeFilter));
    primeFilter[0] = 0;
    primeFilter[1] = 0;
    for (int i = 2; i <= 4000000 ; i++)
    {
        if (primeFilter[i]){
            for (int j = 2*i; j <= 4000000; j+=i)
                primeFilter[j] = false;
        }
    }

    int lPointer = 2;
    int rPointer = 2;
    int sum = 2;
    int N;
    int found = 0;
    std::cin >> N;
    while (lPointer <= N){
        if (sum < N)
        {
            while(!primeFilter[++rPointer]);
            sum += rPointer;
        }
        else if (sum > N)
        {
            sum -= lPointer;
            while(!primeFilter[++lPointer]);
        }
        else
        {
            found++;
            sum -= lPointer;
            while(!primeFilter[++lPointer]);
        }
    }
    std::cout << found;
    
}

소수를 구한 배열은 배열의 값으로 소수를 찾는게 아니라, 인덱스로 찾게 되므로 R L 값을 증가시킬 때 해당 배열이 NULL이 아닐때까지 계속 증가시켜주도록 구현하였다.

투 포인터 문제중에 스탠다드 접근인 것 같다. 조금 꼬아진 문제를 이제 풀어봐야겠다.

 

오늘도 평온한 하루가 되길. 슨민.