greedy
-
7 - 1. 우체국CS/ProblemSolving 2022. 3. 6. 16:19
https://acmicpc.net/problem/2141 2141번: 우체국 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 X[1], A[1], X[2], A[2], …, X[N], A[N]이 주어진다. 범위는 |X[i]| ≤ 1,000,000,000, 0 ≤ A[i] ≤ 1,000,000,000 이며 모든 입력은 정수이다. www.acmicpc.net 최근에 푼 그리디 문제 중에, 코테에서도 종종 봤던 유형인 것 같아 이번 기회에 기억에 남길겸 정리해보려 합니다. 문제는 읽기 귀찮으니까 대충 그림으로 표현해서 보겠습니다. 아래와 같이 수직선 상 X 좌표에 마을이 존재하고, 각 마을에는 A명의 사람들이 살고 있습니다. 각 사람들의 거리의 합이 최소가 되는 위치에 우체국을 ..