[백준/BOJ] 백준 13209번 : 검역소

https://www.acmicpc.net/problem/13209 13209번: 검역소 3번 도시와 5번 도시를 잇는 도로와 4번 도시와 3번 도시를 잇는 도로에 검역소를 설치하면 치료제를 11 인분만 비축해도 된다. 1번 도시에 전염병이 발생할 경우 1번 도시와 3번 도시의 10명의 사 www.acmicpc.net 이분 탐색을 이용하여 트리의 각 그룹들을 mid명 이하로 만들 수 있는지 체크하는 방법으로 문제를 해결했다. 체크하는 방법은 트리를 리프 노드에서부터 올라가면서 확인해 가며 그룹을 만들어 가는데 그룹의 인원이 가능한 최대 인원을 넘으면 최적으로 가능한 부분만 남기고 나머지는 검역소로 간선을 자르는 방법으로 나아갔다. 자른 횟수가 자를 수 있는 횟수를 넘었는지 안 넘었는지 확인하는 방식으로 ..

2021.09.01