[백준] 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는 정수이다.

출력

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

 

하얀 티셔츠는 N개, 세일러 카라는 M개 있습니다.

각 티셔츠에 대해 붙일 수 있는 카라를 배열로 정리합니다.

 

이분매칭 복습입니다.

이분매칭은 A집단과 B집단을 연결하는 이분그래프에서, 가장 많이 짝지을 수 있는 경우를 찾는 문제입니다.

이 문제같은경우 ,티셔츠 집단과 스커트 집단을 나누어, 길이 폭을 기준으로 연결 할 수 있는 케이스를 저장하고,

이분매칭을 수행합니다.

 

이분매칭 알고리즘은 다음과 같습니다.

DFS와 유사합니다.

티셔츠 1번부터 N번 까지 한번씩 수행하여, 짝이 맞는 스커트가 있는지 확인합니다.

Dfs(k)에 대해, 

bool dfs(int k){ //k번째 티셔츠를 확인합니다. 반환형 bool type
	if(visited[k])return false; // 해당 dfs에서 방문한 티셔츠인경우 더이상 진행 X
    for(auto r:adj[k]){ //k번째 티셔츠에대해 r개의 짝이맞는 스커트를 확인합니다.
    	if(!s[r] || dfs(s[r])){
        // 1. 만약 s[r]이 없는경우, r번째 스커트는 현재 주인이 없으므로 k번째 셔츠와 매칭 가능
        // 2. 만약 s[r]은 있지만, r번째 스커트의 현재 주인을 바꿀 수 있다면 k번째 셔츠와 매칭 가능
        	s[r]=k;
            return true; //true 반환
        }
	}
   	return false;
    //매칭 불가
}

 

 

이분매칭을 이용해서 최대 매칭수를 구하면 됩니다.

#include<bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false),cin.tie(NULL);
#define mset(v) memset(v,0,sizeof(v));
#define rep(i,a) for(int i=0;i<a;++i)
#define REP(i,a) for(int i=1;i<=a;++i)
#define all(v) v.begin(), v.end()
using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef tuple<int, int, int>ti;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
int dy[] = { -1,0,1,0 }, dx[] = { 0,1,0,-1 }, INF = 987654321;
int N, M, W[201], w, SW[1001], v[201], s[1001];
vi adj[201];
bool canS(float w, float sw) {
	if ((w / 2 <= sw && sw <= w * 3 / 4) || (w <= sw && sw <= w * 5 / 4))return 1;
	return 0;
}
bool dfs(int t) {
	if (v[t])return false;
	v[t] = 1;
	for (int r : adj[t]) {
		if (!s[r] || dfs(s[r])) {
			s[r] = t;
			return true;
		}
	}
	return false;
}
int main() {
	FAST;
	cin >> N >> M;
	REP(i, N)cin >> W[i];
	REP(i, M)cin >> SW[i];
	REP(i, N)REP(j, M)if (canS(W[i], SW[j]))adj[i].push_back(j);
	int cnt = 0;
	REP(i, N) {
		mset(v);
		if (dfs(i))
			cnt++;
	}
	cout << cnt;
}