[Baekjoon Online Judge] 백준 1644번 소수의 연속합(Python)

© 2020 All Rights Reserved. 주식회사 스타트링크

[Baekjoon Online Judge] 백준 1644번 소수의 연속합

(Python)

(글쓴날 : 2020.05.13)

 

---

* Baekjoon Online Judge, 백준 1644번 문제 Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.

---

 

 

백준 1644번 소수의 연속합

---

1) 문제

문제 링크 : https://www.acmicpc.net/problem/1644

1644번: 소수의 연속합

---

2) 풀이 과정

* 시간 복잡도 : O(n log log n)

 

어떤 자연수가 주어지고, 해당 값까지의 소수들 중 합이 다시 원래의 값이 되는 경우의 수를 구하는 문제입니다.

 

저의 경우, 투 포인터를 적용하였고, Python을 사용했습니다.

만약, 시간 복잡도가 O(n²)인 완전 탐색을 적용할 경우 N의 최댓값이 4,000,000이므로 시간 초과가 발생하게 됩니다.

따라서, 에라토스테네스의 체를 이용해 주어진 자연수까지의 소수 리스트를 구한 후, 투 포인터를 적용하여 연속된 소수들의 합이 해당 값이 되는 경우의 수를 구해 문제를 해결했습니다.

---

3) 코드

 

* Python 코드

import sys
input = sys.stdin.readline
 
N = int(input())
isPrime = [False, False] + [True] * (N - 1)
primeSequence = []
 
for i in range(2, N + 1):
    if isPrime[i]:
        primeSequence.append(i)
        for j in range(2 * i, N + 1, i):
            isPrime[j] = False
 
startPointer = 0
endPointer = 0
sumValue = 0
ans = 0
 
while(True):
    if sumValue >= N:
        sumValue -= primeSequence[startPointer]
        startPointer += 1
    elif endPointer == len(primeSequence):
        break
    else:
        sumValue += primeSequence[endPointer]
        endPointer += 1
 
    if sumValue == N:
        ans += 1
 
print(ans)

---