[백준] 1644 - 소수의 연속합 (G3)

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

1644번: 소수의 연속합

나는 투포인터를 안쓰고 풀었는데, 정해가 투포인터라서 놀랐다.

확실히 '어떤 정렬된 것들중 일부의 연속' 은 투포인터를 쓰기 좋다.

 

일단 이 문제가 골드3이라서 당연히 DP부터 의심했는데, DP가 아닌 풀이가 떠올라서 바로 구현했다.

내가 푼 풀이와 투포인터 풀이를 모두 적어보겠다.

 

이분탐색을 이용한 풀이

 

소수의 리스트 2, 3, 5, 7, 11, 13, ,,,, 가 있다고 하고 소수의 누적합 배열을 s 라고 해보자.

(누적합 배열은 0부터 시작한다고 하자)

 

최적해가 되는 구간은 어떤 소수로 시작할 것이다.

2로 시작하는 구간의 합이 최적해가 되려면 이 구간의 마지막 소수는 어떤 값일까?

이 구간의 마지막 소수를 k번째 소수라고 해보자. (2는 1번째 소수)

 

그러면 2부터 k번째 소수까지의 합은 누적합을 이용해 s[k] - s[0] 이 된다.

그리고 이게 최적해라면 s[k] - s[0] = 찾는수 가 될 것이다.

이 식을 변형하면 s[k] = 찾는수 + s[0] 이다.

 

그럼 이 조건에 맞는 k는 어떻게 찾을 수 있을까?

간단하다. 이분탐색을 이용하면 log n 시간에 찾을 수 있다.

 

하지만 최적해 구간은 2로 시작하지 않을 수 있다.

3으로 시작할 수도 있고, 5로 시작할 수도 있고, ,,,, , 찾는 수가 소수라면 찾는 수로 시작할 수도 있다.

따라서 이걸 2, 3, 5, ,,, 소수 리스트에 대해 반복해준다.

 

찾는 수가 최대 400만인데, 2부터 400만까지 소수의 개수는 28만 3148개이다.

소수 리스트의 사이즈가 대략 10^5 이고, 위 알고리즘의 시간복잡도는 O(n log n) 이므로 시간내에 풀 수 있다.

 

n = int(input())
primeList = []
isPrime = [True]*(n+1)
for i in range(2, n+1):
    if isPrime[i]:
        primeList.append(i)
        for j in range(i+i, n+1, i):
            isPrime[j] = False

s = [0]
sum_value = 0
for prime in primeList:
    sum_value += prime
    s.append(sum_value)

answer = 0
for i in range(len(s)):
    find = n + s[i]
    start, end = 0, len(s)
    while start < end:
        mid = (start + end) // 2
        if s[mid] < find:
            start = mid + 1
        else:
            end = mid

    if end < len(s) and s[end] == find:
        answer += 1


print(answer)

파이썬3으로 약 3.6초

pypy3로 0.6초에 통과한다.

 

투 포인터를 이용한 풀이

 

다음으로 투포인터 알고리즘은 더 간단하다.

(이게 골드 3이라고..?)

누적합 배열의 인덱스를 가리키는 포인터 2개 p1, p2에 대해

sum_value = s[p2] - s[p1] 이다.

이 sum_value 랑 찾는 값을 비교해서

찾는 값보다 작으면 p2를 늘리고, 아니면 p1 을 늘리면된다.

(그냥 투포인터 + 누적합 섞은 문제다..)

 

p2 포인터가 범위밖으로 벗어날때까지 반복하면서 개수를 세주면 된다.

n = int(input())
primeList = []
isPrime = [True]*(n+1)
for i in range(2, n+1):
    if isPrime[i]:
        primeList.append(i)
        for j in range(i+i, n**0.5 + 1, i):
            isPrime[j] = False

s = [0]
sum_value = 0
for prime in primeList:
    sum_value += prime
    s.append(sum_value)

answer = 0
p1, p2 = 0, 0
while True:
    if p2 == len(s):
        break

    if s[p2] - s[p1] <= n:
        if s[p2] - s[p1] == n:
            answer += 1
        p2 += 1
    else:
        p1 += 1


print(answer)

파이썬으로 약 2.1초

pypy3으로 약 0.6초의 시간을 보여준다.

시간차이가 확연히 난다.

 

투포인터 알고리즘의 시간복잡도는 O(n)이다.

O(n log n)이 비록 정해는 아니었지만, pypy의 시간차이가 너무 미미해서 이 두 시간복잡도 사이에 정답이고 아니고를 가르려면 소수의 범위를 더 넓혀야 할 것 같기도 하다.

(심지어 에라토스테네스의 체를 전체 소수에 대해 돌렸는데도 통과되니..)