방금 백준 P1 찍었다. 정말 열심히였어..
그래서 다이아까지 달리기 전, 잠깐 쉬어 갈까 한다.
쉴 겸해서 쉬운 문제 하나 풀이를 적어보겠다.

BOJ 18138 - 리유나는 세일러복을 좋아해 링크
(2022.09.07 기준 P5)
(리유나도 나도 치팅은 싫어해)

문제

N개의 하얀 티셔츠와 M개의 세일러 카라가 있고, 하얀 티셔츠의 너비 w라고 하면 세일러 카라의 너비는 w/2 이상 w×3/4 이하이거나 w 이상 w×5/4 이하면 하얀 티셔츠에 세일러 카라를 붙여 세일러복 하나를 만든다고 하면
최대로 만들 수 있는 세일러복 개수

알고리즘

하얀 티셔츠와 세일러 카라를 조건에 맞게 최대한 매칭시키는 것이므로 이분 매칭

풀이

너무나도 간단한 이분 매칭.
베이직한 이분 매칭 문제는 매칭이 되는 상대가 주어지지만 이 문제는 매칭이 되는 상대를 직접 구해야 한다.

문제에서 제시한 매칭 조건은 다음과 같다.

만약 최대 유량 방식으로 한다면, 세일러복과 조건에 맞는 모든 카라를 간선으로 이어주고 source에서 세일러복으로의 용량은 1, 카라에서 sink로의 용량은 1로 잡고 유량을 흘러서 sink로의 최대 유량을 구하면 답이 나온다.

하지만 이분 매칭만 사용해보자.
베이직한 이분 매칭 문제는 매칭이 되는 상대가 주어져서 그 상대들만 매칭이 되는지 확인했다면, 이 문제는 일단 모든 카라를 체크해야 한다.
이 때, 방문 여부(visited) 검사와 동시에 문제에 주어진 너비 조건도 같이 검사하여 부합한다면 매칭을 시도하는 것이다.

이분매칭(티셔츠):
	tw = 티셔츠의 너비
    for 카라 in 전체 카라:
    	kw = 카라의 너비
        if visited[카라] == false && (tw / 2 <= kw <= tw * 3 / 4 || tw <= kw <= tw * 5 / 4)

이런 느낌으로 시도하면 된다.

저 이분 매칭 함수가 성공했으면 세일러복이 하나 만들어진 것이므로 출력값에 1을 더해주자.
이런 방법으로 모든 티셔츠에 대해 매칭을 시도하여 만들어진 세일러복 개수(출력값)을 출력해주면 끝!

코드

import sys; input = sys.stdin.readline

def match(p): # 이분 매칭
    tw = t[p] # 티셔츠의 너비
    for q in range(M):
        kw = k[q] # 카라의 너비
        if not visited[q] and (tw / 2 <= kw <= tw * 3 / 4 or tw <= kw <= tw * 5/ 4): # 문제의 조건에 부합하면 매칭 시도
            visited[q] = True
            if connect[q] == -1 or match(connect[q]):
                connect[q] = p
                return True
    return False

N, M = map(int, input().split())
t = [int(input()) for _ in range(N)] # 티셔츠의 너비
k = [int(input()) for _ in range(M)] # 카라의 너비
connect = [-1] * M
answer = 0
for i in range(N): # 티셔츠 차례대로 이분 매칭 시작
    visited = [False] * M
    if match(i): # 이분 매칭이 성공했을 경우
        answer += 1 # 세일러복 하나 만들기를 성공한 것이다.
print(answer)

여담

이 문제 풀이 적다가 느닷없이 피치피치핏치? 그 만화가 생각이 났다.
라떼는 말야, 내 또래인 여자애들은 이 만화 모르는 사람이 없을 정도로 인기가 많았단 말이지.
초등학교 때 반 친구인 남자애 하나가 컴퓨터실에서 만화 안 변신 장면만 돌려보다가 걸려서 놀림받았던 애가 있었는데 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ 잘지내니...?
뾰로롱