연속하는 소수의 합을 구해보자!
(제목만 봐도 기피하게 되는 문제)

BOJ 7512 - 연속하는 소수의 합 링크
(2022.09.30 기준 G3)
(치팅하면 평생 수학쪽 코딩만 하게 됨)

문제

숫자 ni가 m개 주어질 때, 연속하는 소수 ni개의 합으로 나타낼수 있는 가장 작은 소수

알고리즘

구간의 크기가 ni로 정해져 있고, 그 구간의 합을 살펴봐야 하기 때문에 슬라이딩 윈도우
소수 판정도 해야 하므로 에라토스테네스의 체를 쓰도록 하자.

풀이

항상 정답이 10**7 보다 작다고 하였으니, 10**7 이하의 소수만 알고 있으면 된다.
그러므로 에라토스테네스의 체를 사용하여 소수의 리스트와 어떤 수가 소수인지 판정할 수 있는 배열을 만들자.

is_prime = [False, False] + [True] * 9999999 # 소수 판정
prime = [] # 소수
for i in range(2, 10000001): # 2부터 10000000까지
    if is_prime[i]: # True이면
        prime.append(i) # 소수에 넣고
        for j in range(i * 2, 10000001, i): # i를 제외한 i의 배수들을 제외하자
            is_prime[j] = False

그리고 슬라이딩 윈도우 함수를 만들자.
무슨 함수냐면, 합이 소수가 될 때까지 미끄러뜨리는 것이다.

def sliding_to_prime(S, s, e): # 합, 시작, 끝
    S += prime[e + 1] - prime[s] # 합에 시작을 빼고 끝 + 1을 넣고
    s += 1; e += 1 # 시작과 끝에 1을 더하자.
    while not is_prime[S]: # 만약 합이 소수가 아니라면
        S += prime[e + 1] - prime[s] # 위 과정을 반복
        s += 1; e += 1
    return [S, s, e]

자 이제 테스트케이스를 입력받자.
m개의 ni를 받으면, ni개의 2부터 시작하는 소수들의 구간의 합들을 구하자.
이 때, 합이 소수가 아니면 슬라이딩 윈도우 함수를 사용하자.

이제부터 중요하다.
만약에 m개의 구간합이 다르다면, 어떻게 해야 할까?
우리는 구간을 맨 앞부터 입력했다. 그러면 뒤로 한칸씩 미끄러뜨려야 하고, 자연스럽게 합은 커지게 된다.
그러면 모든 구간합이 같아지러면? 구간합이 제일 작은 것을 미끄러뜨려야 한다는 말이다.
그러니깐 힙을 사용하자.
힙에 구간합과 시작과 끝을 저장하고, 모든 구간합이 같지 않으면 제일 작은 구간합을 pop하여 미끄러뜨리고 다시 힙에 넣는 것이다.
이 과정을 모든 구간합이 같아질 때까지 반복하고 출력하면 되는 것이다.

코드

import sys; input = sys.stdin.readline
import heapq

# 합이 소수가 될 때까지 슬라이딩시키는 함수
def sliding_to_prime(S, s, e): # 합, 시작, 끝
    S += prime[e + 1] - prime[s] # 합에 시작을 빼고 끝 + 1을 넣고
    s += 1; e += 1 # 시작과 끝에 1을 더하자.
    while not is_prime[S]: # 만약 합이 소수가 아니라면
        S += prime[e + 1] - prime[s] # 위 과정을 반복
        s += 1; e += 1
    return [S, s, e]

def solve():
    m = int(input())
    N = list(map(int, input().split()))
    result = []
    for n in N:
        S = sum(prime[:n]) # n 크기의 구간합
        s = 0; e = n - 1 # 시작은 0, 끝은 n - 1
        if is_prime[S]: # 만약 합이 소수라면
            heapq.heappush(result, [S, s, e]) # 그대로 push
        else: # 합이 소수가 아니면
            heapq.heappush(result, sliding_to_prime(S, s, e)) # 슬라이딩 후 push

    # 모든 합이 같지 않으면
    # 제일 작은 값을 pop하고 슬라이딩 후 push
    # 모든 합이 같아질 때까지 반복
    while True:
        for i in range(m - 1):
            if result[i][0] != result[i + 1][0]: # 같지 않으면
                S, s, e = heapq.heappop(result) # pop
                heapq.heappush(result, sliding_to_prime(S, s, e)) # 슬라이딩 후 push
                break # 반복
        else: # 모든 합이 같으면
            print(result[0][0]) # 값 출력
            print() # 빈 줄도 출력
            break

# 에라토스테네스의 체
is_prime = [False, False] + [True] * 9999999
prime = []
for i in range(2, 10000001):
    if is_prime[i]:
        prime.append(i)
        for j in range(i * 2, 10000001, i):
            is_prime[j] = False

for i in range(1, int(input()) + 1):
    print('Scenario %d:' % i)
    solve()

여담

소수 문제는 다방면하게 많이 나오는 것 같다. 개인적으로 소수 문제를 별로 좋아하지 않는다. 그래도 친해져야겠지..?