sort
-
1029. Two City SchedulingAlgorithm/LeetCode 2020. 6. 4. 13:17
출처: leetcode.com/problems/two-city-scheduling/ 분류: Greedy, Easy 접근방식 각 cost에는 A와 B에 보낼 수 있는 비용이 들어있습니다. 2N개의 비용이 적힌 costs에서 각각 N개씩 공평하게 A와 B에 나눌 때 최소비용을 찾는 문제입니다. costs가 [[10,20],[30,200],[400,50],[30,20]] 이렇게 주어져 있다면, A에 2개 B에 2개를 [ 10, 30, 50, 20 ]로 뽑아줄 때 가장 최소비용이 됩니다. 하지만 무작정 둘 중 최소를 찾아서 분배한다고 해서 최소비용을 보장할 수가 없습니다. costs 중에서 어떤 cost를 우선적으로 분배해줘야 할까요? 바로 둘의 차이가 큰 cost를 먼저 분배해줘야 나중에 더 작은 비용을 분배..