[백준(파이썬/Python)] 1644_소수의 연속합(투 포인터, 에라토스테네스의 체)

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

1644번: 소수의 연속합

 

N이 클 때 소수 판별을 효율적으로 할 수 있는 에라토스테네스의 체와 투포인터 개념을 활용하는 문제입니다.

 

에라토스테네스의 체는 소수 판별할 때 대표적인 알고리즘으로 "임의의 정수 x가 소수라면, x의 배수는 소수가 아니다"라는 명제를 이용해 구현하는데요. 이를 구현하는 방법은 아래 코드에서 prime_list() 함수로 구현되어 있습니다.

 

한편, 문제에서 구하고자 하는 것은 어떤 수 N을 연속한 소수의 합으로 나타낼 수 있는 경우의 수입니다.

 

따라서, 에라토스테네스의 체로 구한 N보다 작은 소수들의 집합을 리스트로 구하고 해당 리스트에서 위 조건을 만족하는 연속하는 소수 구간이 있는지 탐색을 진행하면 되겠죠.

 

하지만 모든 경우를 다 탐색하려면 O(리스트의 길이^2)만큼의 시간이 소요되기 때문에 시간복잡도 측면에서 효율적이지 못합니다.

 

따라서 투 포인터로 효율적인 탐색을 해야 되는데, 저 같은 경우에는 포인터의 끝점을 리스트 길이의 마지막에 두고 시작을 했습니다. 그리고 시작 포인터를 끝점과 동일하게 두고 왼쪽으로 이동시켜보면서 구간의 합을 구했습니다.

 

구간 사이의 합이 N이 된다면 경우의 수를 하나 증가시키면 되고 N보다 커지게 된다면 그 아래로는 시작 포인터를 움직일 필요가 없으므로 끝 포인터를 왼쪽으로 한 칸 이동시켜서 구간 사이 합을 줄여보면 됩니다.

 

풀이는 아래와 같습니다.

 

[풀이]

# 에라토스테네스의 체
def prime_list(n):
    isPrime = [True] * (n+1)

    m = int(n ** 0.5)
    # n 제곱근 이하의 수에 대해서 i가 소수인 경우 i의 배수들은 소수가 아님
    for i in range(2, m + 1):
        if isPrime[i] == True:
            for j in range(i+i, n+1, i): 
                isPrime[j] = False

    # 소수 목록 리턴
    return [i for i in range(2, n+1) if isPrime[i] == True]


n = int(input())
answer = 0
prime_number = prime_list(n)

# 끝 포인터를 소수 집합의 맨 마지막에 놓고 시작
endCursor = len(prime_number) - 1
while endCursor >= 0:
    for startCursor in range(endCursor, -1, -1):

        # 연속된 소수의 합
        totalSum = sum(prime_number[startCursor:endCursor+1])
        if totalSum == n:
            answer += 1
        
        # 연속된 소수 합이 n보다 크면 끝 포인터를 왼쪽으로 이동
        elif totalSum > n:
            break

    endCursor -= 1
print(answer)