[BOJ][백준]이분 매칭-18138번 리유나는 세일러복을 좋아해

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

18138번: 리유나는 세일러복을 좋아해

 

문제

리유나는 세일러복을 정말 좋아한다. 그래서 세일러복을 많이 많이 만들어서 다른 사람들에게도 입히려고 한다.

세일러복을 만들기 위해서는 두 가지 재료가 필요하다. 바로 하얀 티셔츠와 세일러 카라이다. 둘을 사용해서 세일러복을 만드는 방법은 다음과 같다.

그림 1: 세일러복의 제작 과정

리유나는 세상 사람들의 하얀 티셔츠를 모두 세일러복으로 만들고 싶었지만, 예산과 시간 등의 부족으로 인해 N개의 하얀 티셔츠만을 구해올 수 있었다. 세일러 카라도 많이 만들어야 했지만, 마찬가지의 이유로 세일러 카라도 M개 밖에 만들지 못했다고 한다.

게다가, 불행히도 세일러 카라를 너무 급하게 만들다 보니까 크기가 들쭉날쭉하게 되었다. 아무 티셔츠에나 아무 세일러 카라를 붙일 수 있는 것이 아니다. 하얀 티셔츠의 너비를 정수 w라고 할 때, 여기에 붙일 수 있는 세일러 카라는 두 가지가 있다. 너비가 w/2 이상 w×3/4이하인 세일러 카라를 붙일 수 있고, 혹은 카라가 옷보다 살짝 더 넓게 만들어서 너비가 w 이상 w×5/4 이하인 카라를 붙일 수 있다. 이 외의 경우는 리유나가 좋아하지 않기 때문에 만들지 않으려고 한다.

리유나는 이런 악조건 속에서도 최대한 많은 세일러복을 만들고 싶어한다. 리유나가 세일러복을 최대 몇개나 만들 수 있는지 알려주자.

입력

첫째 줄에는 가지고 있는 하얀 티셔츠와 세일러 카라의 개수가 주어진다. (1 ≤ N, M ≤ 200)

두번째 줄부터 n개의 줄에는 각 하얀 티셔츠들의 너비 w가 주어진다. (1 ≤ w ≤ 1,000)

다음 n+2번째 줄부터 m개의 줄에는 각 세일러 카라들의 너비 w가 주어진다. (1 ≤ w ≤ 1,000)

둘 모두 너비 w는 정수이다.

출력

첫째 줄에 만들 수 있는 세일러복 개수의 최댓값을 출력한다.

 

******************************************************************************************************************

 

기본적인 이분매칭 유형에 약간의 변형을 준 문제입니다. 보통 이분매칭 문제들은 a집단과 b집단의 연결된 상태를

주고, 그때의 매칭 최댓값을 구하는데, 이문제는 조건을 주고 연결을 직접 한 다음 문제를 풀어라고 지시합니다.

다행히 그 조건이 까다롭지않으니 간단한 전처리로 간선을 연결해 준 후, 이분매칭을 dfs함수로 검사하며 

세일러복을 최대한으로 맞춰보면 되겠네요. 일반적으로 a집단에서 b집단을 검사하는 것 과 달리, 문제조건상 b집단에서 a집단을 매칭하는 것이 더 간단하므로 헷갈릴 수 있지만 a집단과 b집단을 계속 구분하면서 생각하며 코드를 작성해 나가면 됩니다.

#include <iostream>
#include <string.h>
#include <algorithm>
#include <vector>
using namespace std;
int n,m,cnt=0;
vector<int>a,b;
vector<vector<int>>adj;
int aMatch[1001],bMatch[1001],visited[1001];

bool dfs(int u)
{
    if(visited[u])return false;
    visited[u]=true;
    for(auto v:adj[u])
    {
        if(aMatch[v]==-1||dfs(aMatch[v]))
        {
            aMatch[v]=u;
            bMatch[u]=v;
            return true;
        }
    }
    return false;
}


int main()
{
    cin>>n>>m;
    a.resize(n),b.resize(m);
    for(int i=0;i<n;i++)cin>>a[i];
    for(int i=0;i<m;i++)cin>>b[i];

    adj.resize(m);
    for(int i=0;i<m;i++)
    {
        for(int j=0;j<n;j++)
            if(((double)b[i]>=(double)a[j]*(0.5) && (double)b[i]<=(double)a[j]*(0.75)) ||
               (b[i]>=a[j] &&  (double)b[i]<=(double)a[j]*(1.25)) )
                adj[i].push_back(j);
    }

    memset(aMatch,-1,sizeof(aMatch));
    memset(bMatch,-1,sizeof(bMatch));

    for(int i=0;i<m;i++)
    {
        memset(visited,0,sizeof(visited));
        if(dfs(i)) cnt++;
    }
    cout<<cnt;
}