[Gold III] 소수의 연속합 - 1644 (소수, 투 포인터)

[Gold III] 소수의 연속합 - 1644

문제 링크

성능 요약

메모리: 201272 KB, 시간: 504 ms

분류

수학(math), 정수론(number_theory), 소수 판정(primality_test), 에라토스테네스의 체(sieve), 두 포인터(two_pointer)

문제 설명

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

• 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을 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 출력한다.

 

풀이방법

문제를 해결하는 데 약 40분 정도 걸린 것 같다. 문제를 풀면서 아쉬웠던 부분은 어떤 알고리즘을 사용해야 하는지 바로 판단을 못했기 때문이다.

일단, 소수 판정은 무조건 들어가야 생각하여 시간 복잡도가 O(n log(logn))인 에라토스테네스의 체를 사용하여 2~N 까지의 소수들을 리스트(array)에 담아주었다.

그 후, '연속'된 소수의 합을 구해야 했으므로, '누적합'을 생각하고 풀었는데 실패했다. 결국, 알고리즘 분류를 보니 '투 포인터'가 사용되는 것을 보고 곧바로 아이디어가 떠올라 구현하게 되었다.

어떠한 알고리즘을 사용해서 문제를 풀어야할 지 판단하는 법은 실전 코딩테스트에서 매우 중요하므로 더욱 연습할 필요가 있다. 그러므로 가끔씩 부족한 알고리즘을 학습하기 위해 알고리즘 분류를 통해 하나만 계속 푸는 것도 좋지만, 랜덤한 문제를 풀면서 어떤 알고리즘인지 판단하는 방법도 지속적으로 익혀야겠다.

 

구현 순서

1. 에라토스테네스의 체를 이용하여 2~N 까지의 소수를 담은 리스트 생성(array)

2. 연속된 소수의 합을 구하기 위해 투 포인터 설정 (left = 0, right = len(array)-1)

3. left 값이 right값을 넘을 때까지 while문을 돌면서 연속된 소수의 합을 담을 변수(h) 생성

4. h가 N과 같을 경우 횟수(cnt) 1 추가

4-1. h가 N보다 커질 경우, 다음 연속된 소수의 합을 구하기 위해 left += 1

4-2. left == right 일 경우, while 문을 종료하기 위해 left += 1

# N까지 소수들의 합을 구해서N이 되는지 확인
import math, sys
input = sys.stdin.readline
N = int(input())
visited = [False, False] + [True]*(N-1) #모든 수가 소수인 것으로 초기화
array = [] # 소수 리스트
cnt = 0 # 횟수

for i in range(2, int(math.sqrt(N)) + 1):
    if visited[i] == True: #i가 소수인 경우 (남은 수인 경우)
        # i를 제외한 i의 모든 배수를 지우기
        j = 2
        while i * j <= N:
            visited[i*j] = False
            j += 1

for i in range(2, N+1):
    if visited[i]:
        array.append(i)

left, right = 0, len(array)-1

while left <= right:
    h = 0
    for i in range(left, right+1):
        h += array[i]
        if h == N:
            cnt += 1
            left += 1
            break
        elif h > N:
            left += 1
            break
        if left == right:
            left += 1
            break
print(cnt)