백준 2110 공유기 c++ (다시풀어보기)

문제

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

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

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

입력

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

출력

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

예제 입력 1 복사

5 3
1
2
8
4
9

예제 출력 1 복사

3

힌트

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

 

 

알고리즘 스터디를 하면서 만난 이분탐색 문제

처음에 문제가 이해가 되지 않아서 한참을 잡고 있었다. 그래서 검색을 통해서 로직을 알게 되었는데

그래도 너무 어려운 문제였다.. 아직은 이진탐색에 익숙하지 않지만 점차 익숙해지고 있는것같다.

 

문제의 로직은 이렇다.

1. 좌표갯수와 공유기 갯수를 입력받는다.

2. 좌표갯수만큼 집을 배열에 담는다.

3. 집의 좌표크기 최댓값을 저장해둔다.

4. 집 배열을 오름차순으로 정렬한다.

5. 이진탐색을 시작한다.

6. 이전집의 좌표와 현재집의 좌표를 빼고 그 거리가 이진 탐색의 mid를 넘으면 공유기를 설치한것으로 간주하고 cnt를 세준다. 그리고 prevhouse의 값에 현재집 좌표를 넣어준다.

7. 총 공유기 설치수가 설치가능수보다 많으면 너무 촘촘하게 설치한것이므로 low값을 mid 값으로 올려준다.

8. 총 공유기 설치수가 설치가능수보다 적으면 너무 널널하게 설치한것이므로 high값을 mid 값으로 낮춰준다.

9. 이진탐색을 하면서 공유기 cnt 수가 설치가능수보다 크거나 같을때마다 정답을 max로 mid값과 비교하여 저장한다.

10. max값을 출력해준다. ->  가장 큰 범위가 출력된다.

 

 

 

10이라고하면

 

while low <= high

low = mid 

high = mid - 1

1 ~ 10 = 11 :  true

mid = 5

1 ~ 5 = 6 : true

mid = 3

1 ~ 3 = 4 : true

mid = 2

1 ~ 2 = 0 : true 

mid = 1

1 ~ 1 = 0 : true

mid = 1

 

while low < high

1 ~ 10 = 11 :  true

1 ~ 5 = 6 : true

1 ~ 3 = 4 : true

1 ~ 2 = 0 : true 

1 ~ 1 = 0 : false