[BOJ 1644] : 소수의 연속합

문제 링크 : https://www.acmicpc.net/problem/1644

1644번: 소수의 연속합

풀이가 매우 직관적이어서 개인적으로 좋다고 생각했던 문제입니다.

코알라 투 포인터 강의영상 에서 나온 2003번 문제에 에라토스테네스의 체를 덧댄 버전입니다.
해결 방법은 정말 깔끔합니다.

1부터 N 사이에 있는 소수들의 배열(리스트)을 미리 만들어 두고, 해당 테이블에 대해 투 포인터 방법을 사용해 인덱스를 움직여가며 부분합이 N이 되는지 검사하기만 하면 됩니다.

저의 경우에는 소수들의 배열을 그냥 문제에서 주어진 범위인 4백만개로 초기화했지만, 그래도 시간 복잡도는 체를 만들 때 O(NlogN) + 투 포인터의 O(N) 으로 충분히 시간 안에 문제를 해결할 수 있습니다.

import sys
import math
input = sys.stdin.readline

isPrime = [True] * 4000001
isPrime[0], isPrime[1] = False, False
sieve = []
left, right = 0, 0
count = 0

N = int(input())


def initSieve():
    for i in range(2, N + 1):
        if isPrime[i]:
            sieve.append(i)
        for j in range(i * i,  N + 1, i):
            isPrime[j] = False


initSieve()


while right <= len(sieve):
    if N == 1:
        break
    if(sum(sieve[left:right]) > N):
        left += 1
    elif(sum(sieve[left:right]) < N):
        right += 1
    else:
        right += 1
        count += 1

print(count)

투 포인터 탐색을 반복하는 조건에만 유의하면 될 듯 하며, 그 외에는 구현에 군더더기가 없는 문제였던 것 같아 풀기 너무 좋았습니다!
모든 코테 문제가 이랬으면 좋겠네요..