백준 1644 소수들의 연속합 (파이썬)

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

 

제출 코드

import sys

def makeSieve(n):
    sqrt = int(n**(0.5))
    temp = [1] * (n + 1)
    for i in range(2, sqrt+1):
        if temp[i] == 1:
            for j in range(i*2, n+1, i):
                temp[j] = 0

    return [i for i in range(2, n+1) if temp[i] == 1]

def solve():
    answer = 0
    input = sys.stdin.readline
    N = int(input())
    primes = makeSieve(N)

    start = 0
    end = 0
    while end < len(primes):
        if sum(primes[start:end+1]) == N:
            answer += 1
            end += 1
        elif sum(primes[start:end+1]) > N:
            start += 1
        elif sum(primes[start:end+1]) < N:
            end += 1
    print(answer)

if __name__ == "__main__":
    solve()

 

결과 및 정리

먼저 에라토스테네스 체로 N 까지의 소수의 개수를 구합니다.

후 투 포인터로 연속합을 구합니다.

 

시간복잡도

에라토스테네스 체 + 투포인터 : O(sqrt(N)logN) + O(N)

lim(n->무한) 일 때 O(N) > O(sqrt(N)logN) 이므로

O(sqrt(N)logN) + O(N) = O(N)

 

저는 카카오 인턴 코테에서 투 포인터를 몰라 시간초과때문에 한 문제를 아쉽게 못풀었습니다 그래서 요즘 투 포인터를 집중적으로 공부 중입니다. 지금은 투 포인터 문제의 유형을 파악해서 생각 보다 위 문제를 풀수 있었는데 결과를 맞추고 골드 3 문제라서  놀랐습니다.

하지만 소수의 합을 에라토스테네스 체로 구할 때 리스트를 1로 초기화한다는 것을 자꾸 0으로 초기화 해서 틀리네요.. 아직 숙련이 덜 된 것 같습니다.