[C#] 백준 1644 소수의 연속 합 (투 포인터)

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

 

주어진 수가 연속된 소수의 합으로 나올 수 있는 경우의 수를 구하는 문제이다. 소수를 구하고, 연속된 수의 합으로 입력한 수 N이 몇 개가 나올 수 있는지에 대해 찾으면 된다.

 

문제 해결 순서는 다음과 같다.

 

1. 입력을 받는다.

2. 입력받은 수를 기점으로 소수를 구한다.

3. 소수의 배열을 투포인터를 통해 연속된 합을 구한다.

 

 

투 포인터

투 포인터는 배열이나 리스트를 두개의 포인터(인덱스)를 이용해 탑색하는 방식이다. 연속된 구간 합이나 특정 조건을 만족하는 쌍을 찾을 때 사용된다. 

 

이 방법을 쓰는 이유는 연속된 합을 찾는 것의 단순한 방식은 이중 반복문인데, 이중 반복문은 시간 복잡도가 오래 걸리기 때문에 효율적인 투 포인터 방식을 사용하는 것이다.

 

투 포인터는 start와 end의 두 가지 포인터를 설정하고, 각 포인터에 맞게 이동하여 조건을 탐색하는 방식이다.

 

1. start와 end를 배열의 0번째인 첫 번째에 둔다.

2. 합을 초기화 시킨다.

3. 합이 기준이 되는 수 N보다 작은 경우 end포인터를 이동시켜 sum에 더해준다.

4. 합이 N보다 클 경우 start를 이동시켜 end와 start의 간격을 줄이고, start 위치 값을 합에서 뺀다.

5. 합과 N이 같은 경우 카운트를 증가시킨다.

 

이를 end가 배열의 끝까지 도달할 때 까지 반복한다.

 

요약하자면, N보다 크거나 같아질 때 까지 배열을 연속해서 합하고, 같을 경우 count를 증가, 초과할 경우 start를 증가시켜 배열을 앞으로 당기고, 합에서 start부분을 빼는 것이다.

 

static int TwoPointers(int N, List<int> primes)
{
    int start = 0;
    int sum = 0;
    int count = 0;

    for(int end = 0; end < primes.Count; end ++)
    {
        sum += primes[end];

        while(sum > N && start <= end)
        {
            sum -= primes[start];
            start++;
        }

        if (sum == N)
            count++;

    }

    return count;

}

 

 

예시인 41은 2, 3, 5, 7, 11, 13 의 합인데, 41의 경우 17, 19... 41 까지 소수가 나열되어 있다. 그렇다면 저 수에 17을 더할 경우 41 + 17 = 58, 41 보다 초과가 될 것이다.

 

이렇게 초과 될 경우 start의 포인터를 첫번째에서 앞으로 옮겨주며, 2부터 순차대로 41보다 같거나 작아질 때 까지 빼준다.

 

0 ~ 6 까지 나열되어있던 start와 end포인터의 범위가 1 ~ 6, 2 ~ 6... 이런식으로 줄어들고 다시 늘어나고 하는 식으로 end가 배열 끝에 도달할 때 까지 체크하는 것이다.

 

정답 

using System;
using System.Linq;

class Program
{
    static void Main()
    {
        int N = int.Parse(Console.ReadLine());

        List<int> primes = Prime(N);

        int count = TwoPointers(N, primes);

        Console.WriteLine(count);
    }

    static List<int> Prime(int N)
    {
        bool[] isPrime = new bool[N + 1];
        List<int> primes = new List<int>();

        for(int i = 2; i <= N; i++)
            isPrime[i] = true;

        for (int i = 2; i * i <= N; i ++)
        {
            if (isPrime[i])
            {
                for(int j = i * i; j <= N; j += i)
                {
                    isPrime[j] = false;
                }
            }
        }

        for(int i = 2; i <= N; i ++)
        {
            if (isPrime[i])
            {
                primes.Add(i);
            }
        }
        
        return primes;
    }

    static int TwoPointers(int N, List<int> primes)
    {
        int start = 0;
        int sum = 0;
        int count = 0;

        for(int end = 0; end < primes.Count; end ++)
        {
            sum += primes[end];

            while(sum > N && start <= end)
            {
                sum -= primes[start];
                start++;
            }

            if (sum == N)
                count++;

        }

        return count;

    }
}