[Algorithm] BaekJoon : 1644. 소수의 연속합 by Python

[문제 바로가기] https://www.acmicpc.net/problem/1644

📌문제 설명

하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수들이 있다. 몇 가지 자연수의 예를 들어 보면 다음과 같다.

• 3 : 3 (한 가지)
• 41 : 2+3+5+7+11+13 = 11+13+17 = 41 (세 가지)
• 53 : 5+7+11+13+17 = 53 (두 가지)

하지만 연속된 소수의 합으로 나타낼 수 없는 자연수들도 있는데, 20이 그 예이다. 7+13을 계산하면 20이 되기는 하나 7과 13이 연속이 아니기에 적합한 표현이 아니다. 또한 한 소수는 반드시 한 번만 덧셈에 사용될 수 있기 때문에, 3+5+5+7과 같은 표현도 적합하지 않다.

자연수가 주어졌을 때, 이 자연수를 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 구하는 프로그램을 작성하시오.

입력
첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000)

출력
첫째 줄에 자연수 N을 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 출력한다.

---

💡 문제 풀이

기존에 풀었던 기본 문제들을 응용하여 해결할 수 있는 문제다.

문제를 해결하기 위해서 두 가지 단계로 나누었으며 각 단계의 해결방법은 다음과 같다.

1. N까지 소수 구하기 - 에라토스테네스의 체
2. 연속된 소수 합이 N인지 확인하기 - 투 포인터

step 1)
N이 최대 4,000,000이기 때문에 '에라토스테네스의 체' 방법으로 소수를 구하는 것이 적합하다고 생각했다.

N+1크기의 배열(numbers)을 만들어 소수에 해당하는 인덱스에는 1 값을 부여했다. → check 함수

step 2)
numbers 배열에 0과 1로 나타낸 소수 여부를 통해 소수이면 candidates 배열에 담았다.

step 3)
candidates 배열에 담은 소수를 기준으로 투 포인터 탐색을 통해 연속된 소수의 합이 N인지 확인한다.

코드는 다음과 같다.

def check(num): # 1 ~ N까지 소수 찾기
    global N
    for idx in range(2*num, N+1, num):
        numbers[idx] = 0

N = int(input())
numbers = [0, 0] + [1] * (N-1)

for num in range(1, len(numbers)):
    if numbers[num]:
        check(num)
        
candidates = [] # N까지 소수를 담을 배열

for idx in range(len(numbers)): # 소수를 candidates 배열에 담기
    if numbers[idx]:
        candidates.append(idx)
        
left, right = 0, 1 # 투 포인터
answer = 0 # 정답을 담을 변수

while left <= right and right <= len(candidates):
    temp = sum(candidates[left:right])
    if temp == N:
        answer += 1
        right += 1
    elif temp < N:
        right += 1
    else:
        left += 1
print(answer)

---