[BOJ] 소수의 연속합(1644) - PYTHON

숫자 N이 주어지면, N보다 작거나 같은 소수들의 연속합으로 N을 만들 수 있는 개수를 출력하는 문제이다.
더하는 소수는 연속된 숫자이다. (3 + 11 = 14는 안된다.)

시간 복잡도: O(N)

1644번: 소수의 연속합

---

풀이 과정

소수의 연속합이 N이 되는 지를 구하려면 N보다 작거나 같은 소수들의 리스트를 구해야 한다. N까지의 소수를 찾는 과정은 에라토스테네스의 체를 활용하면 O(N)의 시간으로 구할 수 있다.

N보다 작거나 같은 소수들의 리스트를 구하면, 이후에는 투포인터 알고리즘을 활용해서 첫 원소에서 마지막 원소까지 각 연속합이 N과 같은 개수를 카운트해주면 된다. 투포인터 알고리즘도 두 개의 포인터로 리스트를 한번 순회하므로 O(N)의 시간이 걸린다.

---

코드

def getPrimeNumList(maxNum):
    checkArr = [True] * (maxNum + 1)
    rt = []
    for i in range(2, maxNum + 1):
        if not checkArr:
            continue
        else:
            for j in range(i + i, maxNum + 1, i):
                checkArr[j] = False
    for i in range(2, maxNum + 1):
        if checkArr[i]:
            rt.append(i)
    return rt
 
N = int(input())
lst = getPrimeNumList(N)
 
cnt = 0
sp = 0
ep = 0
temp = 0
 
while sp < len(lst):
    if temp < N:
        if ep == len(lst):
            break
        temp += lst[ep]
        ep += 1
    elif temp >= N:
        if temp == N:
            cnt += 1
        temp -= lst[sp]
        sp += 1
print(cnt)

주석 추가

def getPrimeNumList(maxNum):  # N보다 작거나 같은 소수의 연속합 구하기 (에라토스 테네스의 체)
    checkArr = [True] * (maxNum + 1)  # 우선 모든 수가 소수라고 가정
    rt = []  # 소수를 담을 리스트
    for i in range(2, maxNum + 1):  # 2 ~ N까지 순회하며
        if not checkArr:  # 해당 수가 소수가 아니라고 이미 판정됐으면 continue
            continue
        else:  # 해당 수가 소수라면
            for j in range(i + i, maxNum + 1, i):  # 그 수의 모든 배수는 소수가 아니라고 체크
                checkArr[j] = False
    for i in range(2, maxNum + 1):  # 2 ~ N까지 순회하며
        if checkArr[i]:  # 소수라고 판정됐으면
            rt.append(i)  # rt에 append
    return rt
 
 
N = int(input())
lst = getPrimeNumList(N)  # N보다 작거나 같은 소수 list 구하기
 
cnt = 0  # 결과
sp = 0  # 시작 pointer
ep = 0  # 끝 pointer
temp = 0  # 현재까지의 누적합
 
while sp < len(lst):  # sp의 위치가 리스트의 길이보다 작다면 계속 반복
    if temp < N:  # 현재까지의 누적합이 N보다 작다면
        if ep == len(lst):  # 만약에 ep가 리스트의 끝까지 같다면 더이상 연속합으로 N을 만들 수 없으므로 break
            break
        temp += lst[ep]  # temp에 ep 값 더하고
        ep += 1  # ep 에 1 더하기
    elif temp >= N: # temp가 N보다 크거나 같을 때
        if temp == N: # temp 가 N과 같다면 cnt에 1 더하기
            cnt += 1
        temp -= lst[sp] # temp에 sp의 값 빼고 sp 값 1 더하기
        sp += 1
print(cnt) # 연속합이 N인 갯수 출력

---

채점 결과

---

새로 알게 된 점

에라토스테네스의 체를 활용해 N보다 작은 소수 리스트를 만들 때 checkarr을 확인하는 과정은 루트N까지만 확인하면 된다. (루트N 이상의 수가 소수가 아니라면 이미 루트N보다 작은 수의 배수이므로 그전에 반복문을 돌 때 소수가 아니라고 체크됨) 

내 코드에서는 checkArr을 보는 과정에서 반복문에서 0 ~ N까지 모두 확인해서 반복을 최대 400만번(N의 최댓값) 2번씩 돌아서 실행시간이 더 오래 걸렸다.