문제 개요
2N명의 사람이 있다고 가정해 봅시다. 어떤 회사가 면접을 진행하려고 하는데, i번째 사람을 도시 A로 보내는 비행 비용은 costs[i][0], 도시 B로 보내는 비용은 costs[i][1]입니다. 우리는 각 도시에 정확히 N명씩 도착하도록 모든 사람을 이동시키는 최소 총비용을 구해야 합니다.
예를 들어 입력 리스트가 [[10, 20], [30, 200], [400, 50], [30, 20]]이라면 출력은 110이 됩니다. 첫 번째 사람은 비용 10으로 도시 A에, 두 번째 사람은 비용 30으로 도시 A에 보내고, 세 번째와 네 번째 사람은 각각 비용 50과 20으로 도시 B에 보내는 것이 가장 효율적인 배정 방법입니다.
풀이 접근 방법
이 문제는 탐욕(Greedy) 알고리즘으로 해결할 수 있습니다. 핵심 아이디어는 두 도시 간 비용 차이가 큰 사람부터 우선적으로 더 저렴한 도시에 배정하는 것입니다. 비용 차이가 큰 사람을 먼저 확정하면, 나머지 사람들은 상대적으로 유연하게 배정할 수 있기 때문입니다. 다음 단계를 따릅니다.
- n := 배열의 크기
- a := n / 2, b := n / 2 (각 도시에 배정 가능한 남은 자리 수)
- |costs[i][0] − costs[i][1]| 기준 내림차순으로 배열을 정렬하고, ans := 0으로 초기화
- i := 0부터 n − 1까지 반복:
- b == 0이거나 (costs[i][0] ≤ costs[i][1]이고 a > 0)이면 → a를 1 감소시키고 ans += costs[i][0]
- 그렇지 않으면 → b를 1 감소시키고 ans += costs[i][1]
- ans 반환
C++ 구현 예시
아래 구현을 통해 풀이 과정을 더 잘 이해할 수 있습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
static bool cmp(vector <int> a, vector <int> b){
return abs(a[0] - a[1]) > abs(b[0] - b[1]);
}
int twoCitySchedCost(vector<vector<int>>& costs) {
int n = costs.size();
int a = n/2;
int b = n/2;
sort(costs.begin(), costs.end(), cmp);
int ans = 0;
for(int i = 0; i < n; i++){
if(b == 0 || (costs[i][0] <= costs[i][1] && a > 0)){
a--;
ans += costs[i][0];
} else {
b--;
ans += costs[i][1];
}
}
return ans;
}
};
main(){
Solution ob;
vector<vector<int>> c = {{10,20},{30,200},{400,50},{30,20}};
cout << ob.twoCitySchedCost(c);
}입력
[[10,20],[30,200],[400,50],[30,20]]
출력
110
복잡도 분석
실행 시간은 정렬 과정이 지배하므로 시간 복잡도는 O(n log n)입니다. 추가적인 자료구조를 사용하지 않으므로 공간 복잡도는 O(1)입니다(입력 배열 자체의 정렬은 제외).