문제 백준 15976번 풀이 문제를 관찰하면, 수열 $ X $의 원소 $ X_{i} $에 곱해지는 수열 $ Y $의 원소들이 연속됨을 알 수 있습니다. $ X_{i} $에 곱해지는 수의 합은 누적합을 사용하여 전처리해두면 빠르게 구할 수 있습니다. 문제는 누적합을 구현할 때 일반적으로 $ sum[i] = i $번째까지 더한 누적합이라고 정의하고 풀게되는데, 이렇게 구현하면 메모리 초과가 발생합니다. 누적합 배열을 $ sum[i] = \{j, value\} $와 같이 두고, 수열 $ Y_{j} $번째 까지 더했을 때 더한 값을 $ value $로 둡시다. 문제에서 인덱스 값의 입력이 오름차순으로 주어진다고 하였으니, 입력 순서대로 $ sum $ 배열을 만드는데, $ O(N) $만 필요합니다. (입력과 함께..

문제 한국정보올림피아드 2013년 고등부 1번 백준 8983번 풀이 사대의 위치와 동물의 위치 간의 거리는 x좌표의 차이와 동물의 y좌표를 더한 값입니다. 또한, 사대는 x축 위에 있기 때문에 y좌표는 어느 사대를 선택하던 변하지 않습니다. 즉, 동물과 가장 가까운 사대를 구하려면 x좌표의 차이가 최소가 되는 사대를 찾으면 됩니다. 동물의 수와 사냥꾼의 수가 최대 100,000이므로 각 동물에 대한 최적의 위치에 있는 사대를 찾을 때 완전 탐색을 하면 TLE가 납니다. 가장 가까운 사대를 찾기 위해 동물의 x 좌표에 대한 이분 탐색을 해봅시다. 이 때, lower_bound를 사용하는 경우 사대의 후보가 2개가 나옵니다. 이 경우에는 lower_bound로 선택된 사대가 정답입니다. 하지만 아래의 경우에..