[백준 1644 파이썬] 소수의 연속합 (골드 3, 투 포인터)

알고리즘 유형 : 투 포인터
풀이 참고 없이 스스로 풀었나요? : X

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

소스 코드(파이썬)

import sys, math
input = sys.stdin.readline

N = int(input())

# 에라토스테네스의 채
arr = [True]*(N+1)
arr[0] = False
arr[1] = False

for num in range(2, int(math.sqrt(N))+1):
    if arr[num]:
        for mul in range(num*2, N+1, num):
            arr[mul] = False

arr = [i for i in range(2, N+1) if arr[i]] + [0]


# 투 포인터(두 포인터 모두 왼쪽에서 시작)
i = 0
j = 0
subtotal = arr[i]
count = 0

while j < len(arr)-1:
    # 연속합이 N과 같으면 카운팅해주고
    # 왼쪽, 오른쪽 포인터 둘 다 한칸 진행
    # 왼쪽만 옮겼을 때, 연속합이 감소하므로
    # 반드시 N보다 작아진다. 즉, 오른쪽 포인
    # 터도 같이 한 칸 옮겨준다.
    if subtotal == N:
        count += 1
        subtotal -= arr[i]
        i += 1
        j += 1
        subtotal += arr[j]
    # 연속합이 N보다 작으면 값을 키워줘야하므로
    # 오른쪽 포인터를 진행
    elif subtotal < N:
        j += 1
        subtotal += arr[j]
    # 연속합이 N보다 크면 줄여줘야하므로
    # 왼쪽 포인터 진행
    else:
        subtotal -= arr[i]
        i += 1
        
print(count)

풀이 요약

1. 먼저 에라토스테네스의 채로 N의 소수를 모두 구해준다.

2. 소수 리스트를 대상으로 투 포인터 알고리즘을 적용하면 된다. 두 개의 포인터가 모두 왼쪽에서 출발한다.

3. 연속합이 N과 같으면 카운팅해주고 두 포인터를 모두 한 칸씩 진행해준다. 어느 한쪽만을 옮겼을 때 반드시 N과 연속합 값이 달라지므로, 두 개를 모두 진행해주는 것이다.

   연속합이 N보다 작으면 더 키워줘야하므로 오른쪽 포인터 이동, N보다 크면 줄여야하므로 왼쪽 포인터를 이동해준다.

배운 점, 어려웠던 점

• 소수 구할 때 일반적인 O($\sqrt{n}$) 알고리즘을 사용했다가 TLE를 받았다.

  이 후 구글링을 통해, 코딩 테스트 분야에서 소수 구할 때는 대부분 에라토스테네스의 채를 활용한다는 것을 알게 되었고, 시간복잡도 측면에서도 더 효율적이라는 것을 배웠다.