문제 링크: https://www.acmicpc.net/problem/2283 2283번: 구간 자르기 1번째 줄에 정수 N, K(1 ≤ N ≤ 1,000, 1 ≤ K ≤ 1,000,000,000)가 주어진다. 2~N+1번째 줄에 각 구간의 왼쪽 끝점과 오른쪽 끝점의 위치가 주어진다. 양 끝점의 위치는 0 이상 1,000,000 이하의 정수이다. www.acmicpc.net 투포인터, 누적합 알고리즘 먼저 모든 구간을 살펴봐야 하고 각 구간에 존재하는 막대기의 총길이가 K가 되도록 하는 조건이 있기 때문에 이 문제는 투포인터와 누적합을 사용해서 해결할 수 있습니다. 원래 모든 구간을 살펴보기 위해선 O(구간의길이^2)의 시간복잡도가 걸리지만, 각 구간에 존재하는 막대기의 총길이가 K가 되도록 하는 조건은..

문제 링크:https://www.acmicpc.net/problem/2015 2015번: 수들의 합 4 첫째 줄에 정수 N과 K가 주어진다. (1 ≤ N ≤ 200,000, |K| ≤ 2,000,000,000) N과 K 사이에는 빈칸이 하나 있다. 둘째 줄에는 배열 A를 이루는 N개의 정수가 빈 칸을 사이에 두고 A[1], A[2], ..., A[N]의 순서로 www.acmicpc.net 누적합, 해시맵 이 문제는 누적합 배열을 만들고 각 i에 대해서 j n >> k; for (int i = 1; i > arr[i]; prefix[i] = prefix[i - 1] + ar..