Q. 1644 소수의 연속 합(feat. 투포인터)

이 글을 쓰는 이유

지난 주에 싸피 13기 코테를 봤다. 물론 코테 공부는 하지 않았지만 예상했던 것보다 쉽다 느껴졌다.

대외비라 자세한 문제는 올릴 수 없지만 투포인터로 풀수 있는 문제가 나왔는데 당시에 도저히 기억이 안나서 DP로 풀었는데 이참에 투포인터를 좀 더 파보자 생각이 들어 이 글을 쓴다.

 

 

정보

난이도: 골드 3

문제 링크

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

 

 

문제 요약

N을 입력 받고 하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수의 갯수를 찾는 문제이다.

 

ex)

• 41 : 2+3+5+7+11+13 = 11+13+17 = 41 (세 가지)

 

간단한 문제이지만 여러 문제가 합쳐져 있다.

1. 소수 목록 구하기

2. 연속된 소수 합 구하기

 

1. 소수 목록 구하기

먼저 소수 목록을 구하기 위해 "에라토스테네스의 체"를 사용했다. 소수를 구하는 가장 효과적인 방법이라 자세히 설명하지는 않겠지만 간단하게 설명하자면

 

모든 수가 소수라고 가정하고(isPrime = true) 0,1은 소수가 아니라 가정한다.
이후 2 ~ 루트 N까지 i를 증가시키며 isPrime = true면 그 숫자는 소수이다.

그렇다면 i*i부터~N까지 i만큼 증가시킨 값들은 모두 i의 배수이기 때문에 isPrime을 false로 바꾼다

 

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

 

i*i부터 하는 이유는 i*k(k<i) 일 때의 숫자는 이미 k * i 단계에서 isPrime이 false가 됐기 때문이다

 

예를 들어 i가 3일 때 3 * 2 가 아닌 3 * 3부터 하는 이유는 i =2 일 때  j = 2 * 3로 이미 isPrime[6]은 false이기 때문이다.

 

 

이 후 소수 리스트만 넣기 위해 List<Integer> prime에 소수를 넣어줬다.

 

List<Integer> prime = new ArrayList<>();
for (int i = 2; i <= N; i++) {
    if (isPrime[i]) {
        prime.add(i);
    }
}

 

2. 연속된 소수 합 구하기

투 포인터 (Two Pointer Algorithm)

- 배열이나 리스트에서 '두 개의 포인터'를 사용하여 '특정 조건을 만족하는 부분 구간'을 효율적으로 탐색하는 알고리즘이다. 일반적으로 배열이나 리스트가 정렬되어 있을 때 사용한다.

- 투 포인터 알고리즘은 보통은 왼쪽 포인터와 오른쪽 포인터를 사용하며, 이들은 각각 탐색 범위의 시작과 끝을 가리킨다.
- 동일한 시점을 기점으로 왼쪽 포인터를 고정한 상태에서 오른쪽 포인터를 이동하고, 조건에 따라 왼쪽 포인터도 이동하며 탐색하는 방식을 가집니다.

 

 

코드

int sum = 0;
int start = 0;
int end = 0;
for (int i = 2; i <= N; i++) {
    if (isPrime[i]) {
        end++;
        sum += i;
        while (sum >= N && start <= end) {
            if (sum == N) {
                answer++;
                break;
            }
            sum -= prime.get(start++);
        }
    }
}

연속된 소수의 합을 계산하기 위해 투 포인터 기법을 사용했다.

연속된 소수기 때문에 가능한 시작과 끝을 설정해줬다.

 

단계는 다음과 같다

 

start = 0, end = 0으로 설정한다.

sum이 N보다 커지거나 같아질까지 소수를 sum에 더하고 end 포인터를 1 증가시킨다.

 

sum이 

sum이 N보다 작아지거나 start가 end보다 커지기 않을 때까지 start 값을 증가시키며 sum에서 해당 값을 뺀다.

이 때 N이랑 같은 연속된 수가 있다면 answer++를 진행한다.

 

예시

N = 18이면 소수 목록은 2,3,5,7,11,13,17이고

 

먼저 초기 셋팅인 start = 0, end = 0에서 N=18보다 커질 때까지 값을 더한다.

2 + 3 + 5 + 7 + 11 = 28까지 더한다

이 때 start = 0,  end = 5다

 

이제 여기서 sum이 N보다 작아질 때까지 앞쪽 소수를 뺀다.

start = 1, end = 5

3 + 5 + 7 + 11 = 26

 

start = 2, end = 5

5 + 7 + 11 = 23

 

start = 3, end = 5

7 + 11 = 18이다 이때 N = sum이므로 answer++한다.

 

이 후 또다시 sum이 N을 넘을 때까지 end를 늘리며 위와 같은 단계를 진행한다.

 

 투 포인터 시간 복잡도

기존에 완전 탐색으로 위 문제를 해결하려면 O(N^2)의 시간 복잡도를 가진다. 하지만 투 포인터 알고리즘은 선형시간 복잡도를 가지므로 효율적이다.