2141. 우체국 (Python)
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 풀이 그리디에 해당하는 문제인데 모르겠어서 다른 사람의 풀이를 참고했다. 우체국의 위치를 구하려면 우체국을 세운 지점 기준으로 왼쪽에 위치한 사람의 숫자와 오른쪽에 위치한 사람의 숫자의 차가 최소가 되는 지점을 찾아야 한다. 먼저 입력으로 받은 마을 위치를 기준으로 오름차순 정렬한 후 처음부터 끝까지 우체국을 세워가며 왼쪽과 오른쪽 사람의 수를 누적합을 사용하여 체크한다. 두 누적..
2022. 6. 4.
