[BOJ] 1644번 - 소수의 연속합

문제 링크

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)

20

41

출력

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

0

3

💡 아이디어

처음 문제를 마주하였을 때는 순조로웠다. 내가 생각한 로직은 다음과 같았다.

• 해당 수보다 작은 소수의 목록들을 쫙 뽑아내자.
• 연속되는 소수의 리스트를 조합 형식으로 만들어내고, 합이 같을 경우 ans라는 변수에 1씩 더해주자.

이렇게 가벼운 마음으로 작성한 코드는 다음과 같다.

sosu = []
def is_prime_num(n):
    for i in range(2, n):
        if n % i == 0:
            return False 
 	sosu.append(n)
    return True 
    
N = int(input())

for i in range(2, N):
	is_prime_num(i)
   
answer = 0
start = 0
end = 0
while end <= len(sosu):
    temp_list = sum(sosu[start:end])
    if temp_list == N:
        answer = answer + 1
        end = end + 1
    elif temp_list < N:
        end = end + 1
    else:
        start = start + 1
        
if is_prime_num(N):
	answer = answer + 1

print(answer)

모든 test case가 모두 맞았기 때문에 당연히 다 맞을 줄 알고 정답을 돌려보았는데 이게 왠걸.

계속 시간 초과가 나는 것이었다. 😫 잘 풀었다고 생각했는데 이럴 때 힘이 쭈우욱..빠지는 듯한 ㅠㅠ
백준에 사람들이 질문을 해놓은 질문 리스트를 주르륵 읽어보니까 소수 판별 과정에서 분명히 시간 초과가 났을 거라는 것을 알게 되었고, 문제 조건을 다시 보니까 4,000,000 * 4,000,000 = 16,000,000,000,000회니까 당연히 시간 초과가 난다는 것을 알게 되었다.. 이런.
그럼 어떻게 소수 판별을 해야 할까? 라고 생각하면서 폭풍 구글링을 한 끝에 알게 된 것은 바로 에라토스테네스의 체이다.

아래 블로그의 글을 참고하였다.
https://this-programmer.tistory.com/409
그래서 소수 판별 과정을 에라토스테네스 체로 개선을 하여 결과로 얻은 코드는 다음과 같다.

👨‍💻 코드 작성

sosu = []
N = int(input())
a = [False, False] + [True]*(N-1)
for i in range(2, int(N ** 0.5) + 1):
    if a[i]:
        a[i*2::i] = [False]*((N-i)//i)

# 소수 배열 생성
for i in range(N+1):
    if a[i] == True:
        sosu.append(i)

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

print(answer)

소수 판별은 에라토스테네스의 체로 진행하고, 내가 가지고 있는 소수 배열을 이용하여 그 합을 비교하면서, 인덱스를 start와 end라는 플래그로 관리하는 방법으로 문제를 풀 수 있었다.