[Algorithm] 1644. 소수의 연속합

1644: 소수의 연속합(투포인터)

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

• 문제 티어 : G3
• 풀이 여부 : Failed
• 소요 시간 : 38:52

정답 코드

import sys
input = sys.stdin.readline

N = int(input())
# 에라토스테네스의 체를 사용한 소수 찾기
is_prime = [True] * (N+1)
is_prime[0], is_prime[1] = False, False # 0과 1은 소수 X
for i in range(2, int(N ** 0.5) + 1):
  if is_prime[i]: # 소수인 경우
    for j in range(i*i, N+1, i):
      is_prime[j] = False
primes = [i for i in range(2, N+1) if is_prime[i]]

left, right = 0, 0
ans = 0
total = 0

while right < len(primes):
  if total < N:
    total += primes[right]
    right += 1
  elif total > N:
    total -= primes[left]
    left += 1
  else: # total == N
    ans += 1
    total -= primes[left]
    left += 1

if is_prime[N]: # N이 소수인 경우
  ans += 1

print(ans)

접근 방식

1. 에라토스테네스의 체로 소수 판별 -> $O(NloglogN)$
2. 투포인터로 left, right 갱신 -> worst : O(N)

접근 시행착오(+ 코드)

import sys
input = sys.stdin.readline

N = int(input())
arr = [2, 3]
for i in range(4, N):
  if i % 2 != 0 and i % 3 != 0:
    arr.append(i)

left, right = 0, 0

ans = 0
if N % 2 != 0 and N % 3 != 0 and N % 5 != 0 and N % 7 != 0:
  ans = 1

while right < N and left <= right:
  total = sum(arr[left:right+1])
  if total == N:
    ans += 1
    left += 1
  if total < N:
    right += 1
  if total > N:
    left += 1

print(ans)

소수의 특징을 한자릿수의 소수로 나눠떨어지지 않는 수로 잡아서 투포인터 연산을 해줬다.

연속 구간의 합이 N과 일치해야 하는지 판단해야하므로 left와 right를 모두 0으로 잡아 조건에 따라 갱신해줬는데 틀렸다 🫠

배운점 또는 느낀점

머리가 띵했던 문제다 🤯 에라토스테네스의 체를 사용하는 문제라구요…?

너무 새로워서 풀이 찾아보면서 재밌었다. 시간복잡도를 이렇게나 단축시킬 수 있다니!

투포인터로 접근하는 방식은 맞았지만! N 이하의 모든 소수를 구하는 방법(에라토스테네스의 체)과, 투포인터의 갱신과정에서 약간의 오류가 있었다.

에라토스테네스의 체로 소수를 찾으면 $O(NloglogN)$ 이라니 내가 작성했던 코드 대비 시간효율이 비약적으로 높아졌다... 외워야겠다!!