[백준] 2110번 : 공유기 설치 ☆

유형 : 이진탐색

 

 

[예제]

5 3
1
2
8
4
9

[출력]

3

---

1. 풀이

출처 : 패스트캠퍼스 - 알고리즘 / 기술면접 완전 정복 올인원 패키지 Online

 

** 핵심 아이디어
1. 집의 개수 N은 최대 200,000이며, 집의 좌표 X는 최대 1,000,000,000이다.
- 값이 10억이상으로 설정된 경우 이진탐색을 고려해보아야 한다.
→ logX나 √X의 시간복잡도를 가진다고 생각하고 방법을 생각해야 한다.

2. 이진 탐색으로 O(N*logX)에 문제를 해결할 수 있다.
- 20만 * 30 = 600만

3. 가장 인접한 두 공유기 사이의 최대 Gap을 이진 탐색으로 찾는다.
- 이진탐색을 재귀적 방법이나 반복적 방법으로 풀 수 있는데, 여기서는 반복적 방법으로 하는 게 편하다.

 

ex. 1 2 4 8 9

* 반복적으로 Gap을 설정하여, C개 이상의 공유기를 설치할 수 있는 경우를 찾는다. (N=5, C=3)

 

① 최대 Gap = 8, 최소 Gap = 1

- 최대 Gap = 9 - 1 = 8, 최소 Gap = 2 - 1 = 1

- 이진 탐색에서는 min, max를 설정하여 중간값을 찾고 이 과정을 반복한다.

- 여기서 최대 Gap과 최소 Gap은 이진탐색에서 각각 max, min을 의미한다.

- Gap = 4  ∵ (1+8)//2 = 4

- 공유기들의 거리 차가 Gap보다 크게 될 수 있도록, 위치를 설정한다.

 

[ 1 ] [ 2 ] [ 4 ] [ 8 ] [ 9 ]

→ 공유기 2개 가능

→ 설치 가능한 공유기의 개수가 C보다 작으므로, Gap을 감소시킨다.

 

② 최대 Gap = 3, 최소 Gap = 1

- 최대 Gap = 4 - 1 = 3, 최소 Gap = 2 - 1 = 1

- Gap = 2  ∵ (3+1)//2 = 2

 

[ 1 ] [ 2 ] [ 4 ] [ 8 ] [ 9 ]

→ 공유기 3개 가능

→ 설치 가능한 공유기의 개수가 C 이상이므로, 현재 Gap을 저장한 후 Gap을 증가시킨다.

 

③ 최대 Gap = 3, 최소 Gap = 3

- Gap = 3

 

[ 1 ] [ 2 ] [ 4 ] [ 8 ] [ 9 ]

→ 공유기 3개 가능

→ 더 이상 Gap을 증가시킬 수 없으므로, 최적의 경우이다.

 

 

n,c = list(map(int, input().split(' ')))

array = []
for _ in range(n):
    array.append(int(input()))
array = sorted(array)

start = array[1] - array[0] # 최소 Gap
end = array[-1] - array[0] # 최대 Gap
result = 0

while(start <= end):
    mid = (start + end) // 2 # mid는 Gap을 의미
    value = array[0]
    count = 1
    for i in range(1, len(array)):
    	if array[i] >= value + mid:
            value = array[i]
            count += 1
    if count >= c: # c개 이상의 공유기를 설치할 수 있는 경우
    	start = mid + 1
        result = mid
    else: # c개 이상의 공유기를 설치할 수 없는 경우
    	end = mid - 1
        
print(result)

- c개 이상의 공유기를 설치할 수 있는 경우

: 더 넓게 설치할 수 있음 → 설치거리를 mid + 1로 설정하여 다시 앞에서부터 설치

- c개 이상의 공유기를 설치할 수 없는 경우(c개보다 미만)

: 더 좁게 설치해야 함 → 설치거리를 mid - 1로 설정

 

참고 : https://hongcoding.tistory.com/3

문제 출처 : https://www.acmicpc.net/problem/2110

2110번: 공유기 설치