ps
[백준] 2831 - 댄스 파티
kariskan
2023. 6. 20. 13:00
https://www.acmicpc.net/problem/2831
2831번: 댄스 파티
남자 N명과 여자 N명이 상근이가 주최한 댄스 파티에 왔다. 상근이는 모든 사람의 키를 알고있다. 각 남자는 모두 여자와 춤을 출 수 있고, 여자는 남자와 춤을 출 수 있다. 모든 사람은 많아야 한
www.acmicpc.net
문제를 살펴보면, 각 성별의 입력은 반대 성별의 입력의 반대 부호와만 연결될 수 있다.
그렇다면 각 성별을 어떻게 연결할지 살펴보자.
만약 음수 부호의 남자를 연결하려고 할 때, 여자는 양수 부호에다가 abs(남자) > 여자 여야 한다.
그렇다면 어떤 순서로 연결해야 할까?
만약 남자의 입력이 -100 -200 -300 이고,
여자의 입력이 110 210 310 이라면 당연히 3개의 쌍을 만들 수 있어야 한다.
즉, 남자의 절댓값이 작은 순으로, 여자의 키가 작은 것과 쌍을 만들어야 한다.
분명히 음수의 여자와 양수의 남자도 똑같을 것이다.
#include <algorithm>
#include <iostream>
using namespace std;
vector<int> wm, wp, mm, mp;
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
int a;
cin >> a;
if (a < 0) {
mm.push_back(a); // 남자이면서 음수
} else {
mp.push_back(a); // 남자이면서 양수
}
}
for (int i = 0; i < n; i++) {
int a;
cin >> a;
if (a < 0) {
wm.push_back(a); // 여자이면서 음수
} else {
wp.push_back(a); // 여자이면서 양수
}
}
sort(mm.begin(), mm.end());
sort(wp.begin(), wp.end());
sort(mp.begin(), mp.end());
sort(wm.begin(), wm.end());
int ans = 0;
int idx = 0;
for (int i = (int)mm.size() - 1; i >= 0; i--) {
if (idx >= (int)wp.size()) {
break;
}
// 양수인 여자 중 자기보다 키가 작다면
if (abs(mm[i]) > wp[idx]) {
idx++;
ans++;
}
}
idx = 0;
for (int i = (int)wm.size() - 1; i >= 0; i--) {
if (idx >= (int)mp.size()) {
break;
}
// 음수인 여자 중 자기보다 키가 크다면
if (abs(wm[i]) > mp[idx]) {
ans++;
idx++;
}
}
cout << ans;
}