백준 문제 풀이 - 소수의 연속합 1644번

📜 문제 이해하기

하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수들이 있다. 몇 가지 자연수의 예를 들어 보면 다음과 같다.
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을 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 출력하자.

✏️ 계획 수립

이 문제는 2개의 단계를 거쳐야 한다.

• 1단계 소수판정
  먼저 N까지의 숫자 중에서 소수들을 골라야 한다. 이 때 시간복잡도를 줄이기위해서 에라토스테네스의 체를 사용하여 소수를 구한다.

• 2단계 부분 합
  부분 합을 구하면서 그 값이 N이 되는지 확인을 해야 한다. 이 때도 자연수 N의 범위가 4백만이기에 O(N), 즉 선형시간에 해결할 수 있는 알고리즘을 사용해야 하는데 이는 투 포인터로 구현하면 문제를 해결할 수 있다.

💻 계획 수행

if __name__ == '__main__':
    N = int(input())
    if N == 1:
        print(0)
    else:
        nums = [1 for i in range(N+1)]
        prime_nums = []
        # 에라토스테네스의 체
        for i in range(2, N+1):
            if nums[i]:
                prime_nums.append(i)
                for j in range(i, N+1, i):
                    nums[j] = 0
        start = 0
        end = 0
        prime_nums_len = len(prime_nums)
        prime_sum = 0
        result = 0

        while True:
            if prime_sum >= N:
                if prime_sum == N:
                    result += 1
                prime_sum -= prime_nums[start]
                start += 1
            else:
                if end == prime_nums_len:
                    prime_sum -= prime_nums[start]
                    start += 1
                else:
                    prime_sum += prime_nums[end]
                    end += 1

            if start == end:
                break
        print(result)

🤔 회고

문제 자체는 소수 판정과 투 포인터의 합체이기에 두 단계만 제대로 해결할 수 있다면 어렵지 않게 풀 수 있는 문제라고 생각된다.