11376. 열혈강호 2

11376번: 열혈강호 2

---

직원에게 할 일을 짝지어 주는 이분 매칭 문제이다. 단 직원이 최대 두 개의 일을 할 수 있다고 하는데, 당황할 필요는 없다. 이분 매칭을 다시 생각해 보자.

 

일반적인 이분 매칭에서는 한 사람당 최대 하나의 일만 짝지을 수 있다. 최대 두 개의 일을 짝지을 수 있다는 말은, 본질적으로 직원 $n$명의 분신(??)이 각각 존재하여 직원과 직원의 분신에 최대 하나의 일을 짝지을 수 있다는 말과 같다. 또는 $2n$명의 직원을 생각하되 두 직원을 하나로 묶어서 봐도 좋다.

 

여러 구현 방법이 있겠지만, 나는 직원 $n$명에게 하나의 일을 매칭해 주고, 같은 과정을 반복하여 하나의 일을 더 매칭해 주었다.

---

시간이 왜 이러지?