[BOJ] 9576

less than 1 minute read

책 나눠주기

9576번 https://www.acmicpc.net/problem/9576

이분매칭을 이용하는 문제입니다.
그리디 알고리즘을 이용해서 풀 수도 있는 것 같지만,
이분매칭을 공부하고 있어서 이분매칭으로 해결했습니다.

사람과 책을 각각 그룹 1, 2로 생각해줍니다.
각 사람이 책 번호가 a이상 b이하인 책을 원한다고 할 때
아래와 같은 이분 그래프를 만들 수 있으므로,

이와 같은 그래프를 이용하여 이분 매칭을 진행해주면 됩니다.

정답 코드 https://github.com/Geniemo/BOJ/blob/master/9576.cpp

Categories:

Updated:

Leave a comment