[백준 2110] 공유기 설치 (자바)

백준 2110번 공유기 설치 (자바)

 

 

 

출처

www.acmicpc.net/problem/2110

2110번: 공유기 설치

 

 

 

문제

도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다.

도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다.

C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오.

 

 

 

입력

첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 한 줄에 하나씩 주어진다.

 

 

 

출력

첫째 줄에 가장 인접한 두 공유기 사이의 최대 거리를 출력한다.

 

 

 

 

입출력 예

입출력 예

 

 

 

힌트

공유기를 1, 4, 8 또는 1, 4, 9에 설치하면 가장 인접한 두 공유기 사이의 거리는 3이고, 이 거리보다 크게 공유기를 3개 설치할 수 없다.

 

 

 

걸린 시간

시간 재는 거 또 깜빡.. 40분~1시간 정도 걸린 것 같다!

 

 

 

접근 방법

오랜만에 이분 탐색 연습을 위해 실버 1문제 과감하게 도전했더니 크흡..

거리를 구해야 하기 때문에 lowerbound와 upperbound를 사용 해나 했지만 필요 없었다.

 

일단 정렬된 상태에서 맨 앞 집은 무조건 포함하고 가야 한다. 이유는 최대 거리를 구하려면 제일 작은 수와 제일 큰 수를 비교하는 것이 정석이기 때문이다. 하지만, 공유기 개수가 2개 이상일 수 있기 때문에 다른  최대 거리를 구해야 한다.

 

1. mid값을 구할 수 있는 최소거리의 후보로 생각하고 , 거리 비교 시 계산에 사용할 left변수에 0번째 원소를 넣는다.

 

2. 1~n-1까지의 원소와 left를 뺀 값이 mid 이상이면 더 긴 거리가 존재하는 것이므로 개수(cnt)를 +1 하고, left변수에 i번째 원소를 넣는다. (i번째 원소를 다음 공유기로 선택했기 때문에 현재 위치에서 다음 공유기와의 거리를 구해야 하기 때문)

 

3. 개수(cnt)가 c개 이상이면 실제 설치될 공유기보다 같거나 많이 설치된 것이기 때문에 결괏값(result)에 mid를 넣고 더 큰 범위를 찾기 위해 다음 start는 mid+1로 변경한다.(오른쪽 영역 탐색)

 

 

 

 

내 코드

 

 

 

고려할 점

1. 이분 탐색 사용할 것

2. 최대 거리의 기준을 정해 값을 비교할 것

3. 개수를 c와 비교하여 결괏값을 구할 것