풀이
M명에 대해 N권의 책을 최대한 많은 학생에게 주는 문제다.
greedy와 bipartite matching 둘다 풀이해보았다.
Greddy
최대한 많은 인원에게 주기 위해서는 최대한 균등하게 나누어서 주어야 한다는 사실은 자명하다.
어떤 기준으로 나누어 줄까?
다음의 경우에 대해 생각해보자.
(a, b)가 { (1, 4), (1, 5), (1, 2) } 일 때의 경우다.
3명 다 a = 1 동일한 상태이고, b만 다른 경우다.
위에서 순서대로 2, 3, 1번 책을 가져가면 3명 모두 다 책을 가지고 갈 수 있고 (1, 5) 구간에 대해서는 다르게 책을 가지고 가는 방법이 존재할 수 있다.
그 중 중요히 여겨야 할 부분은 바로 a가 동일한 3명에 대해서도 구간(b)이 작은 순서대로 가져가는 방법이 최소한 주어진 구간( (1, 5) )에 대해서는 간단하면서도 최선의 선택일 것이다.
만약 그렇지 않는다면, (1, 4) 는 1번을, (1, 5)는 2번을 가져가고, (1, 2)는 가져갈 수 있는 책이 없다.
이제 코드로 구현을 해보자.
입력받은 M명이 희망하는 책 번호에 대해 a를 기준으로 정렬하는 경우 b가 크면, (a + 1, b)는 책을 가지고 갈 수 없는 상황이 생긴다.
때문에, a <= b 이므로 b를 기준으로 정렬을 한 후 책을 가져가야 위와 같은 상황이 발생하지 않는다.
정렬된 배열에 대해 책을 순서대로 주자.
Bipartite Matching
bipartite matching 분류 중 가장 난이도가 낮아 해당 방식으로도 풀이해봤다.
N권에 대해 M명이 최대 1 ~ N권의 책을 희망한다.
따라서 match, visited의 최대 크기를 N을 기준으로 해주어야 한다.
이 문제 같은 경우에는 N과 M의 차이에 관계없이 M명이 최대 N번 책까지 고를 수 있기 때문에 N > M이더라도 M을 N으로 변경하면 안된다.
소스코드
출처
9576번: 책 나눠주기
백준이는 방 청소를 하면서 필요 없는 전공 서적을 사람들에게 나눠주려고 한다. 나눠줄 책을 모아보니 총 N권이었다. 책이 너무 많기 때문에 백준이는 책을 구분하기 위해 각각 1부터 N까지의
www.acmicpc.net
'PS > Baekjoon Online Judge' 카테고리의 다른 글
| [백준 1298] 노트북의 주인을 찾아서 [Python] (0) | 2023.06.14 |
|---|---|
| [백준 11375] 열혈강호 [Python] (1) | 2023.06.14 |
| [백준 21335] Another Eruption [Python] (0) | 2023.06.12 |
| [백준 21736] 헌내기는 친구가 필요해 [Python] (0) | 2023.06.10 |
| [백준 17106] 빙고 [Text] (3) | 2023.06.10 |