[알고리즘][Python] 백준 1644 소수의 연속 합 문제 풀이

문제 출처 : www.acmicpc.net/problem/1644

1644번: 소수의 연속합

---

문제 해석 : 어떠한 소수를 연속된 소수의 합으로 표현 할 수 있는 경우의 수를 구하여 반환하는 문제이다.

 

문제 풀이 : 이 문제를 풀기 위해서는 2가지 알고리즘을 적용해야 한다.

1. 에라토스테네스의 체 : 주어진 N까지의 소수를 미리 구한다. ( 모든 경우를 체크해서 소수를 만들 경우 시간 초과가 발생합니다. )

2. 투포인터 : start, end 두 개의 포인터를 이용해서 원하는 값보다 작은 경우 end += 1을 큰 경우에는 start += 1을 적용해서 end가 N이 될때까지 수행합니다.

---

풀이 코드

import math

N = int(input())

a = [False, False] + [True] * (N-1)
prime_num = []

for i in range(2, N+1):
    if a[i]:
        prime_num.append(i)
        for j in range(2*i, N+1, i):
            a[j] = False

answer = 0
start = 0
end = 0
while end <= len(prime_num):
    temp_sum = sum(prime_num[start:end])
    if temp_sum == N:
        answer += 1
        end += 1
    elif temp_sum < N:
        end += 1
    else:
        start += 1

print(answer)

---

author : donghak park
contact : donghark03@naver.com

## 문제의 저작권은 백준 알고리즘 사이트에 있습니다. 혹시 문제가 되는 부분이 있으면 연락 바랍니다.