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;
}