날짜: 2022년 5월 13일 오후 2:37
오답: o
코드
Algorithm/81305.py at main · Junroot/Algorithm
풀이
문제 해석을 다르게 해야되는 과정이 어려웠다. 모든 간선을 잘라보는 것은 당연히 시간초과가 발생한다.
- 각 그룹의 인원을 L명 이하로 만들기 위해서 몇 개의 그룹이 필요한지 구하는 문제로 바꾸고,
- 이 그룹의 수가 처음으로 k가되는 L을 바이너리 서치로 풀어야된다.
L의 범위가 (총 인원/ k)~(총 인원) 사이라는 것을 알면 바이너리 서치로 접근할 수 있다.
1번 소문제를 해결하기 위해서 dfs를 이용했다.
현재 노드를 루트 노드로 하는 서브 트리에서 L명 이하로 만들기 위한 (그룹의 개수, 루트 노드를 포함한 그룹의 인원 수)를 반환하는 함수를 만들어 자신의 부모 노드가 자신을 하나의 그룹으로 합칠 수 있는지 판별하여 최대한 적은 그룹을 만들도록 계산한다.
1번 과정에서 O(log(len(num)) 이 필요하고,
2번 과정에서 O(log(sum(num)) 이 필요하다.
len(num)의 최대값 == 10000
sum(num)의 최대값 == 100000000