[leetcode][1029] Two City Scheduling

문제 : https://leetcode.com/problems/two-city-scheduling/

---

2N명을 도시 A, B에 각각 N명씩 이동시키려고 한다. 각각 A, B로 이동시키는 비용이 주어질 때 이동시키는 비용의 최소값을 구해라.

---

A아니면 B로 이동시킨다. -> 둘 중 하나는 선택되어야 한다.

하나는 선택되어야 하므로 한 명의 A, B 이동 비용을 비교해야 되고 두 방법 중 이동 비용이 작은쪽으로 이동시켜야 이득이다. 

각자 A로 이동시키는 비용 - B로 이동시키는 비용을 구해서 오름차순으로 정렬한다. (B가 A보다 크거나, A비용이 더 크지만 B와의 비용 차이가 별로 나지 않을 수록 앞에 정렬된다.) 

앞에서부터 N명은 A로, 그 뒤 N명은 B로 이동시킨다.

 

시간복잡도는 O(NlogN).

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/easy/1029.%20Two%20City%20Scheduling.cpp

---

easy 문제인데도 괜찮은 문제인 듯.