문제 백준 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 $, 오..

문제 백준 1806번 풀이 투포인터, 누적합(map), 분할정복을 사용하여 풀 수 있습니다. 이 문제의 경우 배열의 모든 원소가 자연수이므로 투포인터 풀이도 가능합니다. 왼쪽(l), 오른쪽(r) 변수와 l ~ r 사이의 합을 저장하는 sum 변수를 만들어 문제의 조건에 맞게 l과 r을 관리하면 됩니다. * sum이 S(문제에서 주어지는 것)보다 크거나 같으면 left를 한칸 오른쪽으로 옮깁니다. * 그렇지 않으면 right를 오른쪽으로 옮깁니다. - 위 과정을 l과 r 모두 n - 1이 될 때까지 반복합니다. 소스코드 #include using namespace std; int main() { cin.tie(0)->sync_with_stdio(0); cout.tie(0); int n, s, ans = 1..

문제 난이도는 솔브드 기준으로 1,2,3,4번 순서대로 브론즈 / 실버 / 골드 / 플레로 잘 배분된 것 같았습니다. ​1번은 정사각형의 변 길이를 2 ~ $ min(N, M) $ 잡고 삼중 for 돌리면 됩니다. 시간 복잡도는 $ O(N^3) $ 가 됩니다. ​2번은 투포인터 또는 분할 정복을 사용하면 됩니다. 비슷한 문제: https://www.acmicpc.net/problem/2003​​ 3번은 $ M $번째 쓰레기가 어디서 태워지는지 알아야하는데, 대부분 최소 공배수로 접근한 것 같습나다. 그리고 대부분이 못 푼 것 같습니다. TMI로 최소공배수를 사용한 접근 방법은 잘 모르겠으나 최소 공배수로 하면 소수(prime number)로 구성된 저격 테케를 만들면, 최소 공배수의 범위가 $ unsig..