백준 1644: 소수의 연속합 (골드 III) - 투 포인터, 에라토스테네스의 체

소수와 결합된 투포인터문제이다. 연속된 수를 찾으므로 두 개의 포인터는 0에서 시작한다고 일반적으로 판단해도 될 것같다.

1644번: 소수의 연속합

문제 요약:

N이 주어졌을 때, 연속된 소수로 이루어진 합의 경우의 수를 찾아라!

• 3 : 3 (한 가지)
• 41 : 2+3+5+7+11+13 = 11+13+17 = 41 (세 가지)
• 53 : 5+7+11+13+17 = 53 (두 가지)
• 20: 7 + 13 은 안됨! 연속된 소수가 아니므로. = 0가지

솔루션:

1. 에라토스테네스의 체로 소수 배열을 만든다. 범위는 최대 400만으로 주어졌다. 일반적인 소수판별(O(N^2))로 구할 수 없다.

2. 두 개의 포인터(left, right)는 소수배열의 index역할을 수행한다. 0에서 시작하는 두 개의 포인터를 설정한다.

3. 두 포인터 간의 리스트를 슬라이싱하여 sum()를 일일히 쓰면 시간복잡도가 크게 증가(최대 O(N))하여 시간초과가 발생한다. 따라서 동적으로 변하는 변수를 통해 조건마다 연산한다.

4. sumNum은 가장 첫 번째 소수인 2로 시작한다. 

5. 먼저 sumNum이 N과 같은지 체크한다. 

6. 같다면 cnt(정답)를 1 증가시키고 left와 right를 모두 1씩 증가시키며 sumNum에 right번째 소수를 더하고 left-1번째 소수를 빼준다. 이때 모두 증가시키는 이유는, 정답과 같은 상황에서 left 혹은 right만 이동시켰을 때, 당연히 N과 같지 않아지기 때문이다.

7. 만약 아니라면 sumNum이 N보다 작은지 큰지를 체크한다.

6. sumNum이 N보다 작다면 right를 하나 증가시키고 sumNum에 해당 인덱스의 소수를 더한다.

7. sumNum이 N보다 크다면 left를 하나 증가시키고 left-1번째의 소수값을 sumNum에서 뺀다.

8. 위 과정을 left가 right를 역전하기 전까지 반복한다.

 

코드, 복붙No!

prime_num_list = []

check = [0 for _ in range(4000001)]
check[0:2] = [1, 1]
for i in range(2, int(4000000**0.5)+1):
    if check[i] == 0:
        for j in range(i*2, 4000001, i):
            check[j] = 1
            
prime_num_list = [idx for idx, val in enumerate(check) if val == 0]
        
N = int(input())

left = 0
right = 0
sumNum = prime_num_list[0]

cnt = 0

while left <= right :
    if sumNum == N:
        cnt += 1
        sumNum -= prime_num_list[left]
        left += 1
    elif sumNum < N:
        if right + 1 < len(prime_num_list):
            right += 1
            sumNum += prime_num_list[right]
        else:
            # right가 끝에 도달했을 때 left만 증가
            sumNum -= prime_num_list[left]
            left += 1
    else:
        sumNum -= prime_num_list[left]
        left += 1 
    
print(cnt)

최적화를 해볼 수 있을 것 같은데, 일단 sumNum에 left를 빼주는 코드가 중복되고, 에라토스테네스의 체 과정을 더욱 절약시켜볼 수 있을 것 같다. 예를들어 i*2부터가 아닌, i*i부터 시작해도 되겠다. 이미 이전에서 처리가 되었으니.