백준 1644번, 소수의 연속합 풀이
문제 백준 1644번 풀이 에라토스테네스 체를 사용하여 구간 $[2, N]$ 사이의 모든 소수를 구해줍니다. 구한 소수를 배열에 오름차순으로 두고, 그 배열의 길이를 $ K $로 둡니다. 어떤 구간이 $ N $이 되는지 찾아봅시다. 첫번째로는 누적합을 사용하여 모든 $ i, j (1 \leq i \leq j \leq N) $에 방문하여 $ psum[j] - psum[i] = N$인지 확인해주면 $ O(K^2) $에 가능합니다. 하지만, $ N $의 범위가 $ 4,000,000 $이므로 $ K $가 $ 10,000 $을 넘어가서 제곱 풀이는 사용할 수 없습니다. 누적합에서는 모든 $i, j$를 방문하지만, 투포인터로 가능한 $i, j$만 빠르게 탐색할 수 있습니다. 투포인터의 왼쪽 포인터를 $ L $, 오..
2020.12.21