[Python 3] 백준 1644-소수의 연속합

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

1644번: 소수의 연속합

투 포인터 알고리즘

자연수 배열의 부분합이 원하는 값이 되는 경우의 수를 구하는 알고리즘.

포인터 2개를 만들어 놓고, 조건에 따라 움직이면서 포인터 2개 간의 원소 합이 원하는 값이 될 때를 모두 확인한다.

길이 N인 배열이 있다고 가정하자. 그리고 2개의 포인터, s와 e가 0을 가리키고 있다.

이하의 조건에 따라, 현재 부분합이 원하는 값보다 작으면서 포인터 e가 오른쪽 끝에 도달할 때까지 이하의 행동을 반복한다.

부분합이 원하는 값 이상일 경우: s 포인터 오른쪽으로 1칸 이동.

부분합이 원하는 값보다 작고, 포인터 e가 오른쪽 끝에 있지 않을 경우: e 포인터 오른쪽으로 1칸 이동.

그 이후 부분합이 원하는 값일 경우 체크한다.

 

문제 풀이

투 포인터 개념을 이용하는 문제 중 (아마) 가장 쉬운 문제.

우선 에라토스테네스의 체를 이용해서 주어진 수보다 작은 소수를 모두 구한다.

그 이후, 그러한 소수들을 모아둔 배열에서 투 포인터 알고리즘을 이용해서 합이 n인 경우가 몇 번 나오는지 체크한다.

import sys

def Eratosthenes(n):
  Primes=[]
  isPrime=[1 for i in range(n+1)]
  isPrime[0]=0
  isPrime[1]=0
  for i in range(2, n+1):
    if isPrime[i]==1:
      Primes.append(i)
      for j in range(i*i, n+1, i):
        isPrime[j]=0
  return Primes

def findSums(n):
  Sieve=Eratosthenes(n)
  length=len(Sieve)
  low=0
  high=0
  ret=0
  while True:
    if sum(Sieve[low:high])>=n:
      low+=1
    elif high==length:
      break
    else:
      high+=1
    if sum(Sieve[low:high])==n:
      ret+=1
  return ret

N=int(sys.stdin.readline())
print(findSums(N))