[LeetCode] 1029번: Two City Scheduling

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

Two City Scheduling - LeetCode

 

easy 문제로 분류되어 있지만 꽤나 머리를 많이 썼던 문제다.

그래도 AC을 받고서 엄청 뿌듯했다.

역시 그리디는 아직도 어렵다.

 

최소의 비용으로 A, B 두 도시에 각각 N명의 사람들이 방문할 수 있는 방법을 찾는 문제다.

따라서 주어진 입력에 대해 A 방문 비용과 B 방문 비용의 차이가 더 큰 사람 순으로 정렬했다.

두 도시에 대한 비용 차이가 클수록, 비용이 더 적은 도시를 방문하는 경우 이득을 많이 취할 수 있기 때문이다.

그렇게 되면 우선적으로 A나 B지역에 방문한 사람이 N명을 넘지 않은 경우에

비용이 더 적게 드는 도시로 방문하면 된다.

만약 이미 한 도시의 방문자가 N명이 된 경우에는 cost값에 상관없이 나머지 도시에 방문하면 된다.

 

bool cmp(const vector<int>&a, const vector<int>&b) {
	int aDif = abs(a[0] - a[1]), bDif = abs(b[0] - b[1]);
	return aDif > bDif;
}

class Solution {
public:
	int twoCitySchedCost(vector<vector<int>>& costs) {
		sort(costs.begin(), costs.end(), cmp);

		int ans = 0;

		int aCnt = 0, bCnt = 0;
		for (int i = 0; i < costs.size(); ++i) {
			if (aCnt < costs.size() / 2 && costs[i][0] < costs[i][1]) {
				ans += costs[i][0];
				aCnt++;
				continue;
			}
			if (aCnt >= costs.size() / 2) {
				ans += costs[i][1];
				bCnt++;
				continue;
			}
			if (bCnt < costs.size() / 2 && costs[i][0]>costs[i][1]) {
				ans += costs[i][1];
				bCnt++;
				continue;
			}
			if (bCnt >= costs.size() / 2) {
				ans += costs[i][0];
				aCnt++;
				continue;
			}
		}

		return ans;
	}
};