문제
강호네 회사에는 직원이 N명이 있고, 해야할 일이 M개가 있다. 직원은 1번부터 N번까지 번호가 매겨져 있고, 일은 1번부터 M번까지 번호가 매겨져 있다.
각 직원은 한 개의 일만 할 수 있고, 각각의 일을 담당하는 사람은 1명이어야 한다.
각각의 직원이 할 수 있는 일의 목록이 주어졌을 때, M개의 일 중에서 최대 몇 개를 할 수 있는지 구하는 프로그램을 작성하시오
입력
첫째 줄에 직원의 수 N과 일의 개수 M이 주어진다. (1 ≤ N, M ≤ 1,000)
둘째 줄부터 N개의 줄의 i번째 줄에는 i번 직원이 할 수 있는 일의 개수와 할 수 있는 일의 번호가 주어진다.
출력
첫째 줄에 강호네 회사에서 할 수 있는 일의 개수를 출력한다..
예제 입력 | 예제 출력 |
5 5 2 1 2 1 1 2 2 3 3 3 4 5 1 1 |
4 |
풀이
이전 문제 [ 백준 2188 ] 축사배정 과 코드 정확히 일치함
똑같은 이분매칭 알고리즘으로 축사배정에서 소 -> 직원, 축사 -> 일 로 바뀌었을 뿐 똑같음
코드 바꿀 필요없이 그대로 복붙
'알고리즘' 카테고리의 다른 글
[ 백준 1671 ] 상어의 저녁식사 (0) | 2021.03.03 |
---|---|
[ 백준 11376 ] 열혈강호2 (0) | 2021.03.01 |
[ 백준 2188 ] 축사 배정 (0) | 2021.03.01 |
[ 백준 1948 ] 임계경로 (0) | 2021.02.27 |
[ 백준 1516 ] 게임 개발 (0) | 2021.02.26 |
댓글