문제 링크입니다: https://www.acmicpc.net/problem/11378
11378번: 열혈강호 4
첫째 줄에 직원의 수 N과 일의 개수 M, 지난달에 받은 벌점의 합 K가 주어진다. (1 ≤ N, M ≤ 1,000, 1 ≤ K ≤ N) 둘째 줄부터 N개의 줄의 i번째 줄에는 i번 직원이 할 수 있는 일의 개수와 할 수 있는 �
www.acmicpc.net
기존의 열혈강호 문제들과 마찬가지로 이분매칭 알고리즘을 통해 풀 수 있는 문제였습니다.
열혈강호: https://jaimemin.tistory.com/1352
열혈강호 2: https://jaimemin.tistory.com/1512
열혈강호 3: https://jaimemin.tistory.com/1513
알고리즘은 아래와 같습니다.
1. 직원을 한 쪽, 업무를 반대 쪽으로 배치하고 우선 직원에 대해 가능한 매칭을 진행합니다.
2. 이후에는 최대한 많이 직원과 업무를 매칭을 해줍니다. (최대 K개 업무이므로 매칭이 불가하다면 K개 미만의 업무를 추가적으로 할 수도 있기 때문에 for문 종료 조건에 worker < N && points < K)
개발환경:Visual Studio 2017
지적, 조언, 질문 환영입니다! 댓글 남겨주세요~
반응형
'알고리즘 > BOJ' 카테고리의 다른 글
| 알고리즘을 풀 때 런타임 에러가 발생하는 이유 (0) | 2020.11.05 |
|---|---|
| 백준 10837번 동전 게임 (0) | 2020.09.03 |
| 백준 11377번 열혈강호 3 (0) | 2020.08.24 |
| 백준 11376번 열혈강호 2 (0) | 2020.08.23 |
| 백준 1052번 물병 (4) | 2020.08.21 |