[BOJ] 1646번 수 고르기 (Python)

📃 문제

[BOJ] 수 고르기 🔗링크

오랜만에 에라토스테네스의 체를 이용해 소수를 구해봤고,
이 외 문제 풀이 방식은 투 포인터를 이용한 기본적인 풀이와 동일했다.

🧠❓ 문제 접근 및 풀이

🐶 1번째 접근

소수 구하기 $O(NloglogN)$ + 연속합 구하기 $O(n)$ 으로 풀 수 있는 문제다.
소수 구하기는 에라토스테네스의 체, 연속합 구하기는 투포인터를 이용했다.

소수를 구한 뒤, 소수로 이루어진 수열 $P_{st}$ 부터 수열 $P_{en}$ 까지의
합 $t$를 자연수 $N$과 비교한다면 아래 3가지 경우의 수가 나오게 된다.

각 경우의 수마다 아래와 같은 동작을 하면,
모든 숫자의 조합을 확인하지 않고 $O(n)$ 으로 문제를 풀 수 있다.

① $t < N$ : $t$ 를 증가시키기 위해 Index $en$ 값을 증가시킨다.
② $t > N$ : $t$ 를 감소시키기 위해 Index $st$ 값을 증가시킨다.
③ $t = N$ : 소수의 합으로 나타낼 수 있기 때문에 경우의 수 $cnt$ 를 증가시킨다.

import sys
input = sys.stdin.readline

N = int(input())

nums = [True] * (N+1)
i = 2
while i*i <= N:
    if nums[i]:
        j = i * i
        while j <= N:
            nums[j] = False
            j += i
    i += 1
P = [n for n, tf  in enumerate(nums) if tf][2:]

st, t, cnt = 0, 0, 0
for en in range(len(P)):
    t += P[en]

    while t >= N:
        if t == N:  cnt += 1

        t -= P[st]
        st += 1
print(cnt)