백준 1644: 소수의 연속합(python)

문제

---

풀이

 

에라토스테네스의 체 알고리즘을 사용해 N 이하 소수들을 배열에 저장한 후, 해당 배열에서 투 포인터 기법으로 부분합을 구하여 풀이한다.

a = [False, False] + [True] * (N - 1)   # [0, 1, 2, 3, ... N]
primes=[]

for i in range(2, N + 1):
  if a[i]:
    primes.append(i)
    for j in range(2 * i, N + 1, i):
        a[j] = False

에라토스테네스의 체로 N 이하 소수를 구해 primes 배열에 저장한다.

primes.sort()

이후 투 포인터를 사용할 것이므로 primes 배열을 오름차순 정렬해 준다.

left, right = 0		# 왼쪽, 오른쪽 인덱스
res = 0

while 0 <= left <= right < len(primes):
    pSum = sum(primes[left: right + 1])

    if pSum == N:
        res += 1
        left += 1
        right += 1
    elif pSum > N:  # 큰 경우 - left 증가
        left += 1
    elif pSum < N:  # 작은 경우 - right 증가
        right += 1

일반적인 투 포인터 문제와 동일하게 풀이한다.

 

전체 코드

N = int(input())

a = [False, False] + [True] * (N - 1)   # [0, 1, 2, 3, ... N]
primes=[]

for i in range(2, N + 1):
  if a[i]:
    primes.append(i)
    for j in range(2 * i, N + 1, i):
        a[j] = False
primes.sort()

left = 0
right = 0
res = 0

while 0 <= left <= right < len(primes):
    pSum = sum(primes[left: right + 1])

    if pSum == N:
        res += 1
        left += 1
        right += 1
    elif pSum > N:  # 큰 경우 - left 증가
        left += 1
    elif pSum < N:  # 작은 경우 - right 증가
        right += 1

print(res)