[백준 1644] 소수의 연속합 : 투포인터 (python / 파이썬)

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

풀이 아이디어)
① 에라토스테네스의 체를 이용하여, n 이하인 소수 리스트 받기
② 투 포인터를 이용해 subsum(부분합)이 N이 넘지 않을 때까지 prime을 연속적으로 더하고, 부분합이 n을 넘었을 경우에는 부분합이 정확히 n인지 체크한 후 그 때 result 값을 1 더하기
③ subsum에서 prime[start]를 뺀 이후, start 포인터를 뒤로 한 칸 이동

import math

def prime_list(n):
    array = [True]*(n+1)
    
    for i in range(2, int(math.sqrt(n))+1): # 2부터 루트n 까지
        if array[i] == True:
            j = 2
            while i*j <= n:
                array[i*j] = False
                j +=1
                
    p = []
    for i in range(2, n+1):
        if array[i]:
          p.append(i)  
    return p

N = int(input())
prime = prime_list(N) # N 이하의 소수 리스트
num = len(prime) # N 이하의 소수 개수

end = 0 # 끝 포인터
result = 0 # 경우의 수
subsum = 0 # 연속된 소수의 부분합


# start를 N 이하의 소수 개수까지 모두 차례대로 증가시키며 반복
for start in range(num):
    # end를 가능한 만큼 이동
    while (subsum < N and end < num):
        subsum += prime[end]
        end += 1
    
    if subsum == N:
        result +=1
    
    subsum -= prime[start]
    
print(result)