백준 온라인 저지, 이분매칭 / 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는 정수이다.

출력

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

제한

예제 입력 1

5 5
1
3
5
7
10
2
4
8
5
6

예제 출력 1

4

너비가 3인 티셔츠와 너비가 2인 세일러 카라를 붙이고, 너비가 5인 티셔츠에 너비가 5인 세일러 카라를 붙이고 너비가 7인 티셔츠에 너비가 4인 세일러 카라를 붙이고 너비가 10인 티셔츠에 너비가 6인 세일러 카라를 붙인다. 이렇게 하면 4개를 만드는 것이 최대이다.

예제 입력 2

1 1
1
100

예제 출력 2

0

만들 수 있는 세일러복이 없으므로 0을 출력한다.

힌트

접근 방법

- 주어진 조건(w/2<=세일러카라<=w*3/4 or w<=세일러카라<=w*5/4)에 따라 이분매칭을 진행하여 만들 수 있는 세일러복의 최댓값을 출력한다.

코드

# https://www.acmicpc.net/problem/18138
# 접근 방법
# 주어진 조건(w/2<=세일러카라<=w*3/4 or w<=세일러카라<=w*5/4)에 따라 이분매칭을 진행하여 만들 수 있는 세일러복의 최댓값을 출력한다.
def dfs(idx):
    if visited[idx]:
        return False
    visited[idx] = True
    for x in t[idx]:
        if c[x] == -1 or dfs(c[x]):
            c[x] = idx
            return True
    return False

n, m = map(int, input().split())
width_t = [int(input()) for _ in range(n)]
width_c = [int(input()) for _ in range(m)]
t = [[] for _ in range(n)]
c = [-1 for _ in range(m)]
for i in range(n):
    w = width_t[i]
    for j in range(m):
        if w/2<=width_c[j]<=w*3/4 or w<=width_c[j]<=w*5/4:
            t[i].append(j)

count = 0
for i in range(n):
    visited = [False for _ in range(n)]
    if dfs(i):
        count += 1
print(count)