[Python] 백준 2110번. 공유기 설치

백준(BEAKJOON) |  알고리즘 분류

이진탐색 #2110번

 

https://www.acmicpc.net/problem/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)가 한 줄에 하나씩 주어진다.

 

 

출력 |

 

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

 

 

 

코드)

 

import sys
 
input = sys.stdin.readline
 
n, c = map(int, input().split())
homes = [int(input().rstrip()) for _ in range(n)]
homes.sort()
 
answer = 0
 
 
def binary_search(start, end):
  while start <= end:
    mid = (start + end) // 2
    current = homes[0]
    cnt = 1
    for i in range(1, n):
      if homes[i] - current >= mid:
        cnt += 1
        current = homes[i]
    if cnt >= c:
      global answer
      start = mid + 1
      answer = mid
    else:
      end = mid - 1
 
 
start = 1
end = homes[-1] - homes[0]
binary_search(start, end)
print(answer)

 

 

 

🥕 이 문제는 계속 시도해보다가 결국 구글링의 도움으로 푼 문제이다. 처음에는 mid 값을 책에서 본 것 처럼 배열의 가운데 값으로 해서 풀려고 했다. 하지만 이 문제의 포인트는 !! mid 값을 집의 간격으로 해서 푸는 것이다!! 

cnt는 이 간격으로 공유기를 설치할 때에 설치할 수 있는 공유기의 개수가 되며, cnt 가 c보다 크거나 같다면 간격을 더 키워서 설치할 수 있다는 의미이다.(우리는 문제에서 목표가 인접한 공유기의 최대거리를 구하는 것이므로)

 

문제를 풀고 의문이 들었던건, if cnt >= c였다. 왜 cnt > c가 아니라 같을 때도 포함하는 걸까?를 고민해보았는데 예외가 있었다.

처음에 mid 값은 start = 1, end =8이어서 4가 된다. mid가 4일 때는 cnt가 2가 되어서 end값이 3이 되고, mid는 2가 된다.

여기서, cnt는 1 2 4 8 9 중에서 4, 8일 때를 만족하여 3이 된다. 만약에 이때 if cnt > c:로 하게 되면 간격이 2일 때가 최대거리라고 생각하게 되며 결과는 2가 출력된다.(정답은 3인데 불구하고..!) 따라서 간격이 다른데 설치할 수 있는 공유기의 개수가 같은 경우가 존재하는 경우를 생각해서 if 조건문이 저렇게 되는거구나 이해했다.