알고리즘 스터디 - 백준 1644번 : 소수의 연속합 (feat. Python)

문제 해석

자연수 N이 주어졌을 때 연속된 소수의 합으로 만들 수 있는 경우의 수를 출력하기

어떤 알고리즘을 써야할까?

1. N이하의 소수 구하기 - 에라토스테네스의 체
2. 연속된 수의 합을 구하기 - 앞뒤 2개의 포인터 이용

1. 에라토스테네스의 채

def prime(n):
    # 초기화 True = 소수로 간주
    sieve = [True] * n
    
    m = int(n ** 0.5)
    for i in range(2, m+1):
        # 소수인 경우 i 이후 i의 배수들을 False 판정
        if sieve[i]:
            for j in range(i+i, n, i):
                sieve[j] = False
    
    # 소수 목록 산출
    return [i for i in range(2, n) if sieve[i] == True]

2. 포인터 이용

• 소수를 구한 후에 소수를 더한 누적합 배열(sum)과
• 앞부터 탐색하는 포인터(pt1)와 뒤부터 탐색하는 포인터(pt2)를 생성한다.
• pt1부터 pt2까지의 합 sum[pt2] - sum[pt1]이
• 1) 원하는 값(n)보다 클 경우 pt2 += 1
• 2) n보다 작을 경우 pt1 += 1
• 3) 같을 경우 result += 1, pt1 += 1

알고리즘 코드

97%에서 런타임에러가 나는데 그 경우 N == 1 인 경우를 체크하지 않아서 그렇다.

def prime(n):
    sieve = [True] * (n+1)
    
    m = int(n ** 0.5)
    for i in range(2, m+1):
        if sieve[i]:
            for j in range(i+i, n+1, i):
                sieve[j] = False
    
    return [i for i in range(2, n+1) if sieve[i] == True]

N = int(input())

if N == 1:
    print(0)
else:
    prime_number = prime(N)
    sum = [0] * (len(prime_number) + 1)
    for i in range(len(prime_number)):
        sum[i+1] = sum[i] + prime_number[i]

    pt1, pt2 = 0, 1
    result = 0

    while (pt1 < len(sum)) and (prime_number[pt2-1] <= N):
        sub = sum[pt2] - sum[pt1]
        if sub == N:
            result += 1
            pt1 += 1
        elif sub > N:
            pt1 += 1
        else:
            if pt2 < len(sum) - 1:
                pt2 += 1
            else:
                pt1 += 1

    print(result)