BOJ 18138(리유나는 세일러복을 좋아해) 풀이

solved.ac 티어 : 플래티넘 5

www.acmicpc.net/problem/18138

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

 

이문제는 아주 쉬운 이분 매칭이라 입력을 받고 너비가 w/2 이상 w*3/4 이하랑 너비가 w 이상 w*5/4인 경우 해당 위치에 값을 넣어주고 이분 매칭 하면 끝난다.

(이 문제 못 풀면 이분 매칭 다시 배워야 된다.)

 

#include <bits/stdc++.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
typedef long long ll;
ll inf=1e9;
vector<ll> l[1001];
ll t[1001],q[1001],ty[1001];
ll n,m;
bool dfs(ll x){
    for(int i=0;i<l[x].size();i++){
        ll y=l[x][i];
        if(t[y]){continue;}
        t[y]=true;
        if(q[y]==0||dfs(q[y])){
            q[y]=x;
            return true;
        }
    }
    return false;
}
int main()
{
    ll c,d,cnt=0;
    scanf("%lld %lld",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%lld",&ty[i]);
    }
    for(int i=1;i<=m;i++){
        scanf("%lld",&c);
        for(int g=1;g<=n;g++){
            if(((double)ty[g]/2<=c && ty[g]*3/4>=c)||(ty[g]<=c && ty[g]*5/4>=c)){
                //printf("%lld %lld\n",g,i);
                l[g].push_back(i);
            }
        }
    }
    for(int i=1;i<=n;i++){
        fill(t,t+1001,false);
        if(dfs(i)){cnt++;}
    }
    printf("%lld\n",cnt);
 
}

딱히 주석도 필요 없을 정도로 쉽다.