on91716   2년 전

몇일동안 고민했던 문제인데 어떤 카테고리에 들어가는지도 감이 안오네요. 일단 완전탐색으로 짰긴 했는데 입력값이 커지면 연상량이 굉장히 커집니다. 고수분들,, 어떤 알고리즘 적용시켜야할지, 비슷한 문제가 있다면 몇번 정도 인지만 알려주세요!ㅠㅠ

코딩테스트에 나왔던 문제인데 그대로 복붙하면 문제가 될 것 같아서 명사정도만 바꿔서 올립니다!

 

문제:

N명의 사람은 각각 카드번호(1~M)까지의 카드 몇 장을 갖고 있습니다. N명은 차례대로 각자 한개의 카드만 제출할 수 있으며, 앞에서 나왔던 카드를 제출할 수는 없습니다. N명의 사람들은 최대 몇장의 카드를 제출할 수 있을지 찾으시오.

입력: 첫째 줄에 사람의 수 N과 카드의 개수 M이 주어진다. 둘째 줄부터 n번째 사람이 갖고있는 카드의 개수와 카드번호가 주어진다. 각 카드번호는 중복되어 입력하지 않는다. 카드번호는 1번부터 M번까지 있으며, N과 M은 모두 100보다 작거나 같은 양의 정수이다.

출력: 최대 제출가능한 카드의 개수를 출력한다.

입력예시 1

4 4

3 1 2 3

2 3 4

1 2

1 2

출력 : 3

lyzqm   2년 전

네트워크 플로우의 이분매칭 문제인것 같습니다.

on91716   2년 전

이분매칭 맞는 것같아요!

처음 들어보는거라서 공부해야겠네요ㅠ

도움주셔서 정말 감사합니다

댓글을 작성하려면 로그인해야 합니다.