[BOJ] 백준 2110 공유기 설치 (Swift)

문제

https://www.acmicpc.net/problem/2110

2110번: 공유기 설치

풀이

C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리의 최대 값을 구해야 합니다.

이분 탐색을 떠올릴 수 있습니다.
이분 탐색을 하기위해 집의 좌표를 오름차순으로 정렬해줍시다.

거리에 주목을 하고, 1부터 집의 최대 거리 차이를 탐색하면서 공유기를 몇개 설치할 수 있는지 확인해봅시다.

공유기는 C개 만큼 설치하여야 하므로, C 이상으로 설치할 수 있는 거리중 가장 최대 값을 구한다면 C개의 공유기를 설치하는 값과 동일할 것입니다.

거리가 1이라면, N개 만큼의 공유기가 설치가 가능하고, 거리가 늘어날 수록 설치할 수 있는 공유기 수가 줄어들 것입니다.

따라서 C개 이상으로 설치할 수 있다면 거리를 늘려주어야 하고, 설치할 수 없다면 거리를 줄여서 설치할 수 있는 공유기 수를 늘려주어서 최대 거리를 구할 수 있습니다.

소스코드

후기

이분 탐색 알고리즘으로 풀이할 수 있는 문제였습니다.
거리에 대해 탐색하는 문제였습니다.