백준 2110번 공유기 설치 C++

 

1. 문제 설명

집 N개가 수직선 위에 있다.

각각의 집에 좌표는 X1 ~ Xn...으로

언제 어디서나 와이파이를 사용하기 위해 각각의 집에 공유기 C개를 설치하려고 한다.

한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다.

C개의 공유기를 N개의 집에 설치하여 가장 인접한 두 공유기 사이의 거리를 최대로 하는 문제이다.

 

우선 입력의 개수가 많기에

해당 코드를 추가해준다.

 

다음 이분탐색으로 문제를 푸는 방법이기에

sort함수로 집좌표 벡터값을 작은 순부터 큰순으로 정렬해주고

left right값을 선언하여 작은값과 큰값 선언과 mid값 선언을 해주어 while문으로 이분탐색을 진행해준다.

 

우선 좌표값의 처음 값은 추가가 된상태로 진행되기에 left는 1로 선언하고

공유기 설치된 수를 알아낼 install의 값도 1로 설정해준다.

 

반복문을 통해 집의 수만큼 반복하며,

if문으로 현재 설치한 공유기의 인접한 거리와 mid값을 비교하여

공유기를 설치해주고

 

설치되어진 공유기 수가 C개 이상만큼 된다면 answer에 max함수를 통해 인접한 거리를 최대치로 해주고

mid의 값을 줄여준다.

C개가 되지 않는다면 mid의 값을 - 1 해주어 인접되는 공유기의 거리값 mid 천천히 줄여준다.