# Chap 15. 이진탐색 - Q29. 공유기 설치

- Author: @mildsalmon
- Published: 2021-10-15
- Updated: 2021-10-16
- Source: http://blex.me/@mildsalmon/%EC%9D%B4%EC%B7%A8%EC%BD%94-%EB%B0%B1%EC%A4%80-chap-15-%EC%9D%B4%EC%A7%84%ED%83%90%EC%83%89-q29-%EA%B3%B5%EC%9C%A0%EA%B8%B0-%EC%84%A4%EC%B9%98
- Tags: 파이썬, 알고리즘, 한빛미디어, 나동빈, 코딩테스트, 문제, 풀이, 백준, 이진탐

---

# 1. 공유기 설치

- 난이도
	- 중
- 풀이 시간
	- 50분
- 시간 제한
	- 2초
- 메모리 제한
	- 128 MB
- 출처
	- [2110번: 공유기 설치 (acmicpc.net)](https://www.acmicpc.net/problem/2110)

### A. 📜 문제

위 백준 사이트에 접속하여 문제를 확인해주세요.
	
### B. 💡 내 답안

##### a. 😊 2차 시도 (성공)

```python

n, c = list(map(int, input().split()))
array = []

for i in range(n):
    array.append(int(input()))

array.sort()

start = 1
end = array[-1] - array[0]

answer = 0

while start <= end:
    mid = (start + end) // 2
    house = array[0]
    count = 1

    for i in range(1, n):
        if array[i] >= house + mid:
            count += 1
            house = array[i]

    if count < c:
        end = mid - 1
    else:
        start = mid + 1
        answer = mid

print(answer)

```

##### b. 🙄 회고

> 내 풀이

- 공유기 c개를 사용하여 만들 수 있는 최대 공유기 영역을 구하면 된다.
- 이런 문제는, 문제에서 제시된 것과 이진 탐색에 사용할 길이를 따로 생각해야 한다.

> 반성

- 문제 이해가 잘 안됬었다.

### C. 🧐 문제 해설

> 이해한 내용을 바탕으로 작성했습니다.

![](https://static.blex.me/images/content/2021/10/15/2021_10_15_9_hs2ycnSHVnLa6RRPLzgv.jpg)

##### a. 책 답안

[python-for-coding-test/3.py at master · ndb796/python-for-coding-test (github.com)](https://github.com/ndb796/python-for-coding-test/blob/master/15/3.py)

# 참고문헌

[1] 나동빈, "이것이 취업을 위한 코딩 테스트다 with 파이썬", 초판, 2쇄, 한빛미디어, 2020년

[2] [2110번: 공유기 설치 (acmicpc.net)](https://www.acmicpc.net/problem/2110). Baekjoon. (accessed Oct 15, 2021)