백준 공유기설치 (1) 썸네일형 리스트형 백준 공유기설치 https://www.acmicpc.net/problem/2110 백준 공유기설치 문제이다. 이진탐색 문제인데 꽤나 신박한 문제였다. 문제를 본 순간 드는 생각은 공유기를 하나하나씩 둬 보면서 경우의 수를 따져보는 것이었다. 다시 말해서 완전탐색으로 풀 수 있는 문제지만 역시 백준문제답게 시간제한이 있으므로 완전탐색보다 빠른 이진탐색을 이용하면 풀 수 있을거라 생각했다. 공유기설치하는 집 사이의 최소거리를 이진탐색으로 찾는것을 생각하는 것이 꽤나 어려웠다. 해결 알고리즘 1. 이진탐색으로 nCurDst를 설정한다. 2. 설정한 nCurDst로 공유기를 다 설치할 수 있는지 확인한다. (CheckDistance()) 3. 공유기를 설치할 수 있으면 더 큰 nCurDst로 다시 탐색하고 해당 nCurDst를.. 이전 1 다음