[ 백준 2110 해설 ] ( python ) 공유기 설치

 

📚 공유기 설치

 

문제

도현이의 집 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개 설치할 수 없다.

 

 

 

 

✍ 접근

• 이분 탐색
• 처음에는 백트래킹을사용해서 풀려고 해서 시간초과가 나왔다

 

 

 

정답코드

# ✨ 입력
import sys
input = sys.stdin.readline
N,C = map(int,input().split())
house = []
for _ in range(N):
    house.append(int(input()))
house.sort()

# ✨ 준비 
lt = 1
rt = house[-1]-house[0]
res = 0

# ✨ 이분 탐색
while lt<=rt:
    mid = (lt+rt)//2
    cur = house[0]
    cnt = 1
    for i in range(1,len(house)):
        if house[i]>=cur+mid:
            cnt+=1
            cur = house[i]
    if cnt >=C:
        lt = mid+1
        res = mid
    else:
        rt = mid-1

print(res)

해설

입력

• 문제에서 나온 값을 입력받는다
• house.sort()로 집을 순차적으로 정렬해준다.

준비

• 가장 최소가 되는 공유기의 거리와 최대가 될 수 있는 공유기의 거리를 lt, rt에 각각 넣어준다
• 결과를 저장하는 res를 만들어준다

이분 탐색

• lt가 rt보다 작을 때
  
  • mid(기준이 되는 거리 값)을 (lt(최소거리) + rt(최대거리)) //2로 만들어준다
    => mid값을 기준으로 공유기를 설치했을 때 공유기가 C 이상이면 mid를 늘려주는 아이디어
  • cur은 기준으로 잡는 house의 위치.
  • for문을 돌면서 1부터 집의 개수까지를 돌아주면서
    • 만약 house[i]값이 cur(현재 집 위치) + mid(기준이 되는 거리 값)보다 클 때
    • 공유기를 하나 더 설치해주고 (cnt+=1)
    • cur을 house[i]로 업데이트해준다 (새로운 기준이 되는 집 위치)
  • 그런데 만약 cnt가 C(공유기의 개수)보다 크거나 같다면
    => lt를 mid+1로 교체해준다.(최소 거리가 커져야 하니까)
    => res또한 계속 업데이트해준다
  • else
    => rt를 mid-1로 교체해준다 (최소 거리가 작아져야 하니까)
• 이렇게 이분탐색을 끝내면 원하는 값을 받아낼 수 있다

 

 

 

 

 

⭐ 배움

• 아무튼 값이 말도 안되게 크다! 싶으면 이분탐색을 생각해보자