백준 1644번 : 소수의 연속합 in Python

1644번: 소수의 연속합

 

www.acmicpc.net

이 문제는 자연수가 주어질 때 해당 자연수를 소수들의 합으로 나타낼 수 있는 경우의 수를 구하는 문제이다.

이전 부분합 문제와 유사하나 수열이 주어지는게 아니기에 우선 주어진 자연수를 이용해 수열을 만들어야 하는데, 이 수열은 주어진 자연수보다 작거나 같은 소수들로 이루어져야 한다. 그래야 이를 이용해 연속된 소수들의 합이 주어진 자연수와 같은지 비교할 수 있기 때문이다. 만약 이 수열만 구한다면, 그 이후는 부분합 문제와 풀이 방식이 거의 똑같다.

그렇다면 자연수가 주어질 때 이 자연수보다 작은 소수들의 수열을 어떻게 만들어야 할까? 이를 만드는 방법 중 하나는 에라토스테네스의 체를 이용하는 것이다. 만약 자연수 N이 주어진 경우 2부터 N까지의 자연수들 중 2의 배수(2는 제외), 3의 배수(3은 제외)를 차례로 지워나가는 방식으로 소수가 아닌 수들을 지워나간다. 그래서 N의 제곱근의 배수(N의 제곱근은 제외)까지 지우면 남은 수들은 N보다 작거나 같은 소수만 남게 된다. 이러한 방법을 에라토스테네스의 체라고 한다.

이를 이용해 주어진 자연수 이하의 소수들의 수열을 만들면 그 이후는 부분합 문제와 거의 동일하다. 단지 부분합 문제는 부분수열 중 가장 짧은 길이를 출력해야 했지만, 이 문제는 소수들의 합이 주어진 자연수와 같은 경우의 수를 세야 하므로 이를 위해 약간의 코드만 변경하면 된다.

이를 코드로 구현하면 다음과 같다.

N = int(input())
# 에라토스테네스를 구현하기 위한 배열
primes_cand = [True for _ in range(N+1)]
for n in range(2, min(2001,N+1)):
    # n이 소수가 되는 경우 
    if primes_cand[n]:
        # n 자체를 제외한 n의 배수들을 걸러낸다.
        for i in range(2*n, N+1, n):
            primes_cand[i] = False
arr = [i for i, j in enumerate(primes_cand) if j == True and i >= 2]
if arr:
    l = 0
    r = 0
    s = arr[0]
    cnt = 0
    while r <= len(arr)-1 and l <= r:
        # 부분합이 N과 같으면 cnt를 1 증가시킨다.
        if s == N:
            cnt += 1
        if s >= N:
            s -= arr[l]
            l += 1
        else:
            if r < len(arr)-1:
                r += 1
                s += arr[r]
            else:
                break
    print(cnt)
# N = 1인 경우 arr가 빈 배열이 돼 위 코드는 에러가 발생한다.
else:
    print(0)