공유기 설치
-
모각코PS / 백준 2110 공유기 설치PS 2022. 6. 22. 15:01
모각코 PS스터디 지난주 알고리즘 스터디 내용 중 대표적인 한 문제를 정리해보려고 합니다. 늘 그렇듯 문제는 알고리즘 대장님께서 선정해주셨습니다.😃 문제와 풀이 문제 링크 : 백준 2110번 - 공유기 설치 👇펼쳐서 코드와 해설 읽기 진짜 할 말이 많은데... 일단 넋두리 & 이분탐색 tip은 마무리로 넘겨두고... 로직의 흐름 부터 보시죠. 로직의 흐름은 이렇습니다. 표본 수가 매우 큽니다. 대강 눈으로만 봐도 판단 횟수가 10억 * 20만이니까, 그리디로는 택도 없습니다. logN의 시간 복잡도로, 대강 열댓번 정도의 탐색으로 끝내야할 것 같습니다. 이를 위해 이분탐색으로 풀 것입니다. 정확히는 파라메트릭 서치를 적용할 거에요. 지금 궁금한 건 거리죠. 최소 거리와 최대 거리를 탐색 범위로 두면 됩니..