[ boj : 2831 ] 댄스 파티

https://www.acmicpc.net/problem/2831

2831번: 댄스 파티

해설 : 골드3 인 문제인데 3까지는 아닌 것 같고 4정도면 적당하지 않을까....하는 뇌피셜?

반박시 니 말이 다맞음!!!!

 

사실 이런문제를 처음 접하게 되면 되게 뜬구름을 잡아야 하는 문제 같게 느껴지게 되기도 합니다.

왜 이렇게 접근하는게 최적인데??라는 물음에 재대로 증명을 할 수 있어야 하지만, 그냥 휴리스틱하게 그렇게 될 것 같아 라는 생각하나만 가지고 접근도 할 수 있어야 하지 않을까 하네요.

 

최대 쌍을 맺어줘야 하는 상황인데, 반대로 최대쌍을 만들 수 없는 경우를 생각해 보죠.

예제 3번을 예시로 들면

이런 그림으로 표현할 수 있는데 만약 1700이상의 남자를 원하는 여자가, 1800이하를 원하는 남자를 선택하지 않고 2200이하를 원하는 남자를 선택하게 된다면???1800이하를 원하는 남자를 선택했을 때 보다 '손해'를 얻게 되는 것입니다. 때문에 각각 정렬해준 다음에 순차적으로 남자,여자 각각 가장 처음으로 겹치면 바로 count 를 해주면 됩니다.

#include<bits/stdc++.h>

using namespace std;

struct info {
	bool sex;
	int pos;

	bool operator < (const info& cur) const {
		return pos < cur.pos;
	}
};

stack<int> man, woman;
vector<info> v;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int n, x;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> x;
		v.push_back({ true,-x });
	}
	for (int i = 0; i < n; i++) {
		cin >> x;
		v.push_back({ false,-x });
	}
	sort(v.begin(), v.end());
	int cnt = 0;
	//for (info u : v)cout << u.pos << " ";
	for (info u : v) {
		//남
		if (u.sex) {
			if (u.pos < 0)man.push(u.pos);
			else {
				if (!woman.empty() && abs(woman.top())<u.pos) {
					cnt++;
					woman.pop();
				}
			}
		}
		//여
		else {
			if (!u.sex) {
				if (u.pos < 0)woman.push(u.pos);
				else {
					if (!man.empty() && abs(man.top())<u.pos) {
						cnt++;
						man.pop();
					}
				}
			}
		}
	}
	cout << cnt;
	return 0;
}