문제 링크입니다: https://www.acmicpc.net/problem/11375
11375번: 열혈강호
강호네 회사에는 직원이 N명이 있고, 해야할 일이 M개가 있다. 직원은 1번부터 N번까지 번호가 매겨져 있고, 일은 1번부터 M번까지 번호가 매겨져 있다. 각 직원은 한 개의 일만 할 수 있고, 각각의 일을 담당하는 사람은 1명이어야 한다. 각각의 직원이 할 수 있는 일의 목록이 주어졌을 때, M개의 일 중에서 최대 몇 개를 할 수 있는지 구하는 프로그램을 작성하시오.
www.acmicpc.net
전형적인 이분매칭(Bipartite Matching) 문제였습니다.
이분매칭에 대해서는 Jason9319님이 정말 설명을 잘해주시고 계십니다.(https://jason9319.tistory.com/149)
직원(worker)와 업무(work)에 대해 이분그래프가 있다고 생각하고 최대한 많이 매칭해주도록 접근을 한다고 생각하면 풀이가 떠오를번한 문제였습니다.
개발환경:Visual Studio 2017
지적, 조언, 질문 환영입니다! 댓글 남겨주세요~
반응형
'알고리즘 > BOJ' 카테고리의 다른 글
| 백준 10804번 카드 역배치 (0) | 2020.03.01 |
|---|---|
| 백준 2108번 통계학 (0) | 2020.02.24 |
| 백준 9322번 철벽 보안 알고리즘 (0) | 2020.02.19 |
| 백준 16673번 고려대학교에는 공식 와인이 있다 (0) | 2020.02.18 |
| 백준 14395번 4연산 (0) | 2020.02.17 |