Notice
Recent Posts
Recent Comments
Link
| 일 | 월 | 화 | 수 | 목 | 금 | 토 |
|---|---|---|---|---|---|---|
| 1 | 2 | 3 | 4 | 5 | 6 | |
| 7 | 8 | 9 | 10 | 11 | 12 | 13 |
| 14 | 15 | 16 | 17 | 18 | 19 | 20 |
| 21 | 22 | 23 | 24 | 25 | 26 | 27 |
| 28 | 29 | 30 | 31 |
Tags
- 쿠링
- 백준
- 프로그래머스
- ProGuard
- relay
- MyVoca
- Coroutines
- android
- Kotlin
- 코루틴
- 코드포스
- livedata
- 암호학
- activity
- TEST
- androidStudio
- Gradle
- Python
- boj
- Compose
- textfield
- Hilt
- Coroutine
- MiTweet
- Rxjava
- Codeforces
- GitHub
- pandas
- AWS
- architecture
Archives
- Today
- Total
이동식 저장소
11376. 열혈강호 2 본문
11376번: 열혈강호 2
강호네 회사에는 직원이 N명이 있고, 해야할 일이 M개가 있다. 직원은 1번부터 N번까지 번호가 매겨져 있고, 일은 1번부터 M번까지 번호가 매겨져 있다. 각 직원은 최대 두 개의 일을 할 수 있고, �
www.acmicpc.net
직원에게 할 일을 짝지어 주는 이분 매칭 문제이다. 단 직원이 최대 두 개의 일을 할 수 있다고 하는데, 당황할 필요는 없다. 이분 매칭을 다시 생각해 보자.
일반적인 이분 매칭에서는 한 사람당 최대 하나의 일만 짝지을 수 있다. 최대 두 개의 일을 짝지을 수 있다는 말은, 본질적으로 직원 $n$명의 분신(??)이 각각 존재하여 직원과 직원의 분신에 최대 하나의 일을 짝지을 수 있다는 말과 같다. 또는 $2n$명의 직원을 생각하되 두 직원을 하나로 묶어서 봐도 좋다.
여러 구현 방법이 있겠지만, 나는 직원 $n$명에게 하나의 일을 매칭해 주고, 같은 과정을 반복하여 하나의 일을 더 매칭해 주었다.
'Problem Solving > BOJ' 카테고리의 다른 글
| 1574. 룩 어택 (0) | 2020.08.03 |
|---|---|
| 9577. 토렌트 (1) | 2020.08.02 |
| 4013. ATM (0) | 2020.07.11 |
| 17435. 합성함수와 쿼리 (0) | 2020.06.30 |
| 3665. 최종 순위 (0) | 2020.06.21 |
'Problem Solving/BOJ' Related Articles
more
Comments