1647번 - 도시 분할 계획
98% 에서 실패하였습니다.
정확히는 잘 모르겠지만,
(1) 0 ~ n-2 까지 MST를 찾아서 2개의 그룹으로 분할하는 방식은 반례가 존재하는 것 같습니다.
(2) 0 ~ n-1 까지 MST 를 찾은 후에 가장 비싼 길 1개를 제거하여 계산하니 100% 성공하였습니다.
저와 유사한 오류 있으신 분 계실 것 같아 글 남깁니다. 감사합니다.
댓글을 작성하려면 로그인해야 합니다.
clumpy 11달 전
98% 에서 실패하였습니다.
정확히는 잘 모르겠지만,
(1) 0 ~ n-2 까지 MST를 찾아서 2개의 그룹으로 분할하는 방식은 반례가 존재하는 것 같습니다.
(2) 0 ~ n-1 까지 MST 를 찾은 후에 가장 비싼 길 1개를 제거하여 계산하니 100% 성공하였습니다.
저와 유사한 오류 있으신 분 계실 것 같아 글 남깁니다. 감사합니다.