[백준][1644] 소수의 연속합

suhan0304·2023년 11월 7일

두 포인터 백준 수학 에라토스테네스의 체 정수론

백준

목록 보기

27/53

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

문제

연속된 소수들의 합으로 나타낼 수 있는 경우의 수를 구하여라
"연속된"이기 때문에 소수 하나를 건너뛰거나, 중복된 소수를 더할 수 없다.

입력

첫째 줄, 자연수 N이 주어진다.

출력

첫째 줄, 연속된 소수의 합 경우의 수를 출력한다.

가장 먼저 소수를 구하는 문제가 공용으로 쓰는 알고리즘이 있다.

에라토스테네스의 체

에라토스테네스의 체란?

소수를 판별하는 알고리즘으로 소수들을 대량으로 빠르고 정확하게 구하는 방법이다. 소수와 관련된 문제가 출제되면 항상 에라토스테네스의 체를 사용할 준비가 되어있어야 한다.

에라토스테네스의 체 과정

에라토스테네스의 체는 가장 먼저 소수를 판별할 범위(Bool형식)만큼 배열을 할당하여, 해당하는 값을 넣어주고, 이후에 배수들을 지워나가는 방법을 이용한다.

배열을 생성하여 초기화한다.
2부터 시작해서 특정 수의 배수에 해당하는 수를 모두 False로 변경한다.
- 이 때 자기자신은 바꾸지 않고, 이미 False인 수는 건너뛴다.
2부터 시작하여 True로 살아남있는 소수들을 모두 출력한다.

def eratosthenes_sieve(N):
    IsPrime[0] = IsPrime[1] = False
    for i in range(2, int(N**0.5) + 1):
        for j in range(i * 2, N + 1, i):
            IsPrime[j] = False
    prime = []
    for i in range(N + 1):
        if IsPrime[i]:
            prime.append(i)

    return prime

이 때 에라토스테네스의 체의 배수의 기준이 되는 i는 $int(N^{0.5})$ +1만큼만 반복한다.
- O( $N^{0.5}$ )의 시간 복잡도로 매우 빠르게 소수들을 모두 찾을 수 있다.

풀이

소수 배열을 에라토스테네의 체로 얻었다고 가정할 때 연속된 소수의 합을 어떤 방식으로 구해야 할까? 투 포인터 방식을 이용해 구현했다. 연속되는 소수이기 때문에 시작점과 끝점의 위치를 안다면 해당 범위의 합을 구할 수 있다.

범위의 합 = N ? ans를 1 늘리고 시작접, 끝점을 +1 해준다.

범위의 합 > N ? 시작점을 +1 해준다.

범위의 합 < N ? 끝점을 +1 해준다.

이러한 시작점, 끝점처럼 두 개의 포인터를 이용한 연산은 "연속된"과 "졍렬된"이 둘다 만족할 때 사용 가능하다.
소수가 정렬된 상태로 prime 배열에 들어가있고 연속된 소수의 합을 구하는 문제이므로 투 포인터를 이용해 빠르게 실행 가능하다.

코드로는 다음과 같이 구현할 수 있다.

ans = 0
start = 0
end = 1
while start < end and end <= len(prime):
    s = sum(prime[start:end])
    if s == N:
        # print(start, end)
        ans += 1
        start += 1
        end += 1
    elif s < N:
        end += 1
    elif s > N:
        start += 1

이러한 투 포인터 방식의 장점은 굉장히 적은 시간으로 O(N)의 시간 복잡도로 계산을 할 수 있다.

결국 s, e가 배열 전체를 한 번 훑으면 끝나기 때문이다.

오류 및 해결

기존에는 반복문을 이용해서 하나만 더하는 경우, 두 개만 더하는 경우, 모든 경우를 따져서 더했을때 N보다 커지면 continue 하는 과정으로 구현을 했으나. N가 최대 4,000,000 들어오면 1을 N번, 2를 N-1번, 반복하고 나면 시간 복잡도가 O( $N^2$ )이나 되기 때문에 실행 시간 초과 오류가 발생했다.

코드

import sys

input = sys.stdin.readline


def eratosthenes_sieve(N):
    IsPrime[0] = IsPrime[1] = False
    for i in range(2, int(N**0.5) + 1):
        for j in range(i * 2, N + 1, i):
            IsPrime[j] = False
    prime = []
    for i in range(N + 1):
        if IsPrime[i]:
            prime.append(i)

    return prime


N = int(input())
IsPrime = [True] * (N + 2)
prime = eratosthenes_sieve(N)
# print(prime)

ans = 0
start = 0
end = 1
while start < end and end <= len(prime):
    s = sum(prime[start:end])
    if s == N:
        # print(start, end)
        ans += 1
        start += 1
        end += 1
    elif s < N:
        end += 1
    elif s > N:
        start += 1

print(ans)