백준 2831 - 댄스 파티

 

 

문제 설명

남자 N명과 여자 N명이 상근이가 주최한 댄스 파티에 왔다. 상근이는 모든 사람의 키를 알고있다. 각 남자는 모두 여자와 춤을 출 수 있고, 여자는 남자와 춤을 출 수 있다. 모든 사람은 많아야 한 사람과 춤을 출 수 있다.

모든 남자는 자신이 선호하는 여자와 춤을 추려고 한다. 각 남자가 선호하는 여자는 두 가지 유형이 있는데, 한 유형은 자신보다 키가 큰 여자이고, 다른 유형은 자신보다 키가 작은 유형이다. 여자도 남자와 마찬가지로 자신이 선호하는 남자와 춤을 추려고 한다. 각 여자가 선호하는 남자도 남자와 비슷하게 두 유형이 있다. (자신보다 키가 큰 남자, 작은 남자) 키가 같은 남자와 여자가 춤을 추는 일은 일어나지 않는다.

이때, 상근이는 각 사람의 키와 선호하는 이성 유형을 알고 있다. 이런 조건을 가지고 춤을 출 쌍을 만들어 주려고 한다. 상근이는 최대 몇 쌍을 만들 수 있을까?

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

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, 남자와 여자의 키와 선호하는 타입이 주어지면, 최대한 많은 커플을 만들어야 한다.

선호하는 타입은 자신보다 키가 큰 경우와 작은 경우 두 가지로 나눠진다.

 

해당 문제를 풀기 위해서는 한 가지 규칙만 세우면 된다.

키가 큰 사람이 자신보다 작은 사람을 선호한다면, 가장 큰 상대를 고르는 것이 유리하다.

키가 작은 사람도 커플이 되어야 최댓값을 구할 수 있기 때문이다.

 

그렇다면 남자와 여자, 큰 사람을 선호하는 사람과 그렇지 않은 사람으로 총 4가지로 분류한다면 문제를 쉽게 풀 수 있다.

남자 중, -부호가 붙은 사람은 자신보다 작은 사람을 선호한다.

해당 사람들만 모은 뒤, 정렬하면 -부호 때문에 키의 역순으로 정렬될 것이다.

2
-1800 -2200
1900 1700

이라 했을 때, {-2200, -1800}으로 정렬된다는 말이다.

그렇다면, 여자 중, -부호가 붙지 않은 사람 중 키가 큰 순으로 선택하면 된다.

즉, -2200이 1900을 선택하고 -1800이 1700을 선택하게 된다.

 

이러한 과정을 남자와 여자 총 2번 진행하면 된다.

---

 

 

 

 

 

전체 코드

#include <stdio.h>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cmath>
#include <climits>
#include <queue>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <set>
#include <list>
#include <bitset>

using namespace std;

int N;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cout.precision(4);

    cin >> N;

    vector<int> minusMale;
    vector<int> plusMale;
    vector<int> minusFemale;
    vector<int> plusFemale;

    for (int i = 0; i < N; i++)
    {
        int tall;
        cin >> tall;

        if (tall < 0) minusMale.push_back(tall);
        else plusMale.push_back(tall);
    }

    for (int i = 0; i < N; i++)
    {
        int tall;
        cin >> tall;

        if (tall < 0) minusFemale.push_back(tall);
        else plusFemale.push_back(tall);
    }

    sort(minusMale.begin(), minusMale.end());
    sort(plusMale.begin(), plusMale.end());
    sort(minusFemale.begin(), minusFemale.end());
    sort(plusFemale.begin(), plusFemale.end());

    int ans = 0;
    {
        auto itr = plusFemale.rbegin();
        for (int i = 0; i < minusMale.size(); i++)
        {
            int male = abs(minusMale[i]);

            while (itr != plusFemale.rend() && male <= *itr)
            {
                itr++;
            }

            if (itr == plusFemale.rend()) break;

            ans++;
            itr++;
        }   
    }

    {
        auto itr = plusMale.rbegin();
        for (int i = 0; i < minusFemale.size(); i++)
        {
            int female = abs(minusFemale[i]);

            while (itr != plusMale.rend() && female <= *itr)
            {
                itr++;
            }

            if (itr == plusMale.rend()) break;

            ans++;
            itr++;
        }
    }

    cout << ans;


    return 0;
}

---