Boj 1727) 커플 만들기

문제

백준 1727

설명

편의상 남자의 수가 더 많다고 하자.

여자와 남자를 성격에 따라 정렬을 하여 순서대로 매칭 시키고, 최적이 되도록 여자들이 매칭된 남성의 인덱스를 증가시켜보자.

여자가 인덱스를 증가시켜야 하는 경우는 두가지이다.

1. 인덱스를 증가시킬 공간이 있어야 한다. 원래부터 빈자리가 있거나 바로 다음 여성이 인덱스를 옮기면 공간이 생긴다. 이는 마지막 여성부터 자리를 옮겨나가면 간단하게 해결할 수 있다.
2. 인덱스를 증가시킬 경우 성격차이가 줄어들어야 한다. 이때 손해를 보더라도 공간을 만들어 이전 여성들이 움직일 수 있게 하여 총 이득이 증가하는 경우를 고려해야한다. 이는 누적합을 이용하면 해결할 수 있다.

위 방법으로 전체 여성에 걸쳐서 한칸씩 움직이면 결국 최적이 도달한다. 다시말해 그리디전략이 성립한다. 왜 그런지는 증명은…

시간 복잡도

O(\(\mathrm{N}\mathrm{M}\))

코드

int f2m[1002];  // female idx => male idx
int dp[1002];

int main()
{
	int n, m;  cin >> n >> m;
	vector<int> males, females;
	for (int i = 0; i < n; i++) cin >> males.emplace_back();
	for (int i = 0; i < m; i++) cin >> females.emplace_back();
	
	// male is more than female
	if (m > n) {
		swap(n, m);
		swap(males, females);
	}

	males.push_back(1e9); 
	sort(males.begin(), males.end());
	sort(females.begin(), females.end());

	for (int i = 0; i < m; i++) f2m[i] = i; f2m[m] = n;
	for (int i = 0; i < n-m; i++) // 최대 n-m 칸 움직일 수 있음
	{
		dp[0] = 0;
		for (int j = 0; j < m; j++)
		{
			int ifOneLeft = abs(males[f2m[j]] - females[j]) - abs(males[f2m[j]+1] - females[j]);
			dp[j+1] = max(dp[j],0) + ifOneLeft;
		}
		for (int j = m-1; j >= 0; j--)
			if (dp[j+1] >= 0 && f2m[j] + 1 < f2m[j+1] ) 
				f2m[j]++;
	}

	int ans = 0;
	for (int i = 0; i < m; i++) ans += abs(males[f2m[i]] - females[i]);
	cout << ans;
}