BOJ 1644: 소수의 연속합 [Python 3]

이번에는 소수의 연속합이라는 골드 3 난이도의 문제를 풀어 보았다.

 

소수판별을 이용하면 쉽게 풀 수 있는 문제이다.

그러나, 두 개의 포인터, 한 마디로 기준을 두 개를 잡고 풀어야 하는 문제여서 독특했다.

n=5*10**6
a=[False,False]+[True]*(n-1)
for i in range(2,n+1):
    if a[i]:
        for j in range(2*i,n+1,i):
            a[j]=False
primes=[]
for i in range(n):
    if a[i]:
        primes.append(i)

n=int(input() )
l,r=0,0
answer=0
while n>=primes[r]:
    sumNum=sum(primes[l:r+1])
    if sumNum>n:
        l+=1
    elif sumNum<n:
        r+=1
    else:
        answer+=1
        l+=1

print(answer)

앞에 부분은 에라토스테네스의 체 알고리즘을 기본적으로 적용했다.

조금 특이한 점은, n의 범위를 5백만으로 설정했다는 것이다.

원래 n의 최대 크기가 4백만이지만, 그렇게 될 경우 4백만이 되기 전 마지막 소수인 3999971이 판별되지 않아 넉넉하게 n의 범위를 정해주었다.

그 이후에, 소수의 합을 정할 최소 인덱스인 l과 최대 인덱스인 r을 정해두었다.

처음에는 모두 0으로 시작하지만, 소수의 합이 너무 작다면 최대 인덱스인 r을 키우고,

너무 크다면 l을 키워서 범위를 줄인다.

만약 해당 수가 목표 수와 같다면, 정답의 수를 하나 키워주고 l 또한 키워줘서 다음 경우의 수를 계산할 수 있도록 한다.