2018. 7. 18. 18:29, 알고리즘/BOJ
https://www.acmicpc.net/problem/9577
시간 - 조각을 매칭시켜두고, Bipartite matching을 돌립니다. 문제는 '최소 시간'을 요구하기 때문에, Hopcroft를 돌릴 때 시간 또한 인자로 받아 그 시간 이후에는 매칭을 하지 않는 방식으로 K초 내에 조각을 다 받을 수 있는지를 확인합니다. 만약 시간이 컸다면 binary search로 구현을 했을텐데 최대 100초라 그냥 linear하게 구했습니다.
'알고리즘 > BOJ' 카테고리의 다른 글
[BOJ] 13974번: 파일 합치기 2 (0) | 2018.07.19 |
---|---|
10254번: Highway (0) | 2018.07.19 |
[BOJ] 1339번: 단어 수학 (0) | 2018.07.19 |
[BOJ] 9576번: 책 나눠주기 (0) | 2018.07.18 |
[BOJ] 1733번: 등번호 (0) | 2018.07.18 |
[BOJ] 1413번: 박스 안의 열쇠 (0) | 2018.07.18 |
Comments