[알고리즘/이진탐색] 백준 BOJ 2110 공유기 설치 문제

9. BOJ 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

5 3
1
2
8
4
9

예제 출력 1

3

힌트

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

 

---

💡나의 문제 풀이

문제 해결 아이디어

• 핵심은 공유기를 설치할 집 사이의 거리를 최대로 만드는 것이다.
• 3개를 설치해야 한다고 하면, start(최소거리=1), end(최대거리)의 중간값이 가장 적절하다.
• 공유기는 2개 이상이므로, 공유기 2대는 우선 가장 자리에 위치한 집에 설치해야 한다. (첫 start, end)
• 3번째 공유기부터는?
  • start와 end사이의 mid와 가장 가까운 곳에 위치한 집에 설치해야한다.
  • 앞집부터 설치한다고 가정하면, (start+end)//2 = mid 거리보다 같거나 커지는 곳이 생기면 바로 집을 설치

 

고려 사항

• 가장 인접한 두 공유기 사이의 거리가 최대 → 최대한 서로 멀리 떨어져야 함

 

 

작성 코드

• solution을 보고 오랫동안 고민해야 이해할 수 있었다.

import sys

# 이진 탐색으로 간격 값 조정하기
def binary_search(arr, start, end):
  while start<=end:
    mid = (start+end)//2
    # print(start,mid,end)
    current=arr[0]
    cnt = 1 # 첫번째 위치에 공유기 하나 설치

    # 반복문 돌며 공유기 설치 가능한 수 탐색
    for i in range(1, len(arr)):
      if arr[i] >= current+mid:
        cnt += 1
        current = arr[i]

    # 간격을 넓히기
    if cnt >= c:
      global answer
      start = mid + 1 
      answer = mid
    # 간격 좁히기
    else:
      end = mid - 1
    
n, c = map(int, sys.stdin.readline().split())
arr = [int(sys.stdin.readline()) for _ in range(n)]

arr.sort()

answer = 0
start = 1 # 최소 간격
end = arr[-1] - arr[0] # 최대 간격

binary_search(arr, start, end)
print(answer)

 

---

답안 코드

[백준] 2110 공유기 설치 파이썬 풀이

 

 

리뷰 및 점검

• 감을 잡지 못해서 결국 sln을 보고 오랫동안 고민해야 그제서야 이해할 수 있었던 문제
• 핵심은 간격이 최대가 되는 것이므로, 이진 탐색을 통해 집 사이의 거리의 최소와 최대 중간의 어떠한 값을 찾아내야 한다.
  • 이진 탐색을 통해 start와 end가 같아질 때까지, 가장 적절한 집과 집 사이의 간격인, 중간값 mid 의 최대값을 찾아내는 것이 목표이다.
• 맨 처음 집부터 끝 집까지 간격 mid만큼 건너뛰어가면서,
  • 공유기 설치 가능한 집의 수 cnt가 c보다 크다면, 간격을 넓힐 필요가 있기 때문에 start의 값이 mid+1로 되어 다시 중간값 mid를 결정하고,
  • cnt가 c보다 작다면, 간격을 다시 좁혀서 더 많은 공유기가 설치될 수 있도록 해야 하므로, end의 값이 mid-1로 되어 다시 중간값 mid를 결정한다.