[알고리즘] 백준 1644 (파이썬)

wonsik·2022년 5월 2일
1

알고리즘

목록 보기
12/15

연속합과 투 포인터를 이용한 문제이다.
소수를 구하는 방법에는 여러가지가 있지만 시간복잡도 상에서 효율적인 에라토스테네스의 체를 이용하여 구한다.

이 문제에서 유의할 점은 입력이 된 숫자 본인도 쓰일 수 있다는 점이다.

나는 에라토스테네스의 체를 사용할 때 소수를 마킹하는 방법을 모든 리스트를 돌면서 나머지가 0인 지점을 마킹했는데 이러면 입력된 숫자가 매우 커지면 각 소수마다 n의 시간이 돌기 때문에 TLE가 뜨게 된다.

따라서 이를 for i in range(i+i, n, i) 즉 i가 소수라면 2i부터 n까지 i의 배수를 마킹하는 것으로 하여 시간복잡도를 줄였다.

나의 풀이

import sys
import math
num = int(sys.stdin.readline())

def primeset(num):

    pr = [0 for i in range(num+1)]

    tar = int(math.sqrt(num))

    for i in range(2, tar+1):
        if pr[i] == 0:
            for j in range(i+i, num+1, i):
                pr[j] = 1

    return [i for i in range(2,num+1) if pr[i] == 0]

li = primeset(num)

# print(li)

prefix = [0]

presum = 0
for i in li:
    presum += i
    prefix.append(presum)
# print(prefix)


left = 0
right = 1
tar = num
ans = 0
num = len(prefix)-1
# print(prefix)

while left < right and right <= num:

    if -prefix[left] + prefix[right] < tar:
        right += 1

    elif -prefix[left] + prefix[right] > tar:
        left += 1
    else:
        # print(prefix[left], prefix[right])
        ans += 1
        left += 1

print(ans)
profile
새로운 기술을 배우는 것을 좋아하는 엔지니어입니다!

0개의 댓글