[백준/2110] 공유기 설치 (Python)

Problem : https://www.acmicpc.net/problem/2110

2110번: 공유기 설치

 

Difficulty : Gold 4

 

Status : Solved

 

Time : 00:37:59

 

---

 

문제 설명

 

 

도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다.

도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다.

C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오.

 

 

입력 및 출력

 

입력

 

첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 한 줄에 하나씩 주어진다.

 

출력

 

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

 

입력 예시

 

5 3
1
2
8
4
9

 

출력 예시

 

3

 

 

---

 

풀이

 

DP를 이용한 풀이로 맨 처음 시도해보았다. 하지만 2차원 DP를 적용할 경우 시간복잡도는 O(NC)가 되고, C <= N이므로 시간초과 및 메모리초과를 피할 수 없었다.

 

다르게 생각해서, 공유기 사이 최소 인접 거리를 dist로 잡았을 때 과연 C개 이상의 공유기를 설치할 수 있는가? 라는 질문으로 접근해 보자. 이는 dist를 매개변수로 하는 이분 탐색 문제로 변화하며, 시간복잡도는 O(NlogN)으로 감소한다.

 

• 집 리스트를 한 번 순회하며(O(N)) dist 만큼의 공유기를 최대한 놓을 수 있을 만큼 놓아 본다.
  • 첫 번째 원소를 시작점(즉 공유기를 무조건 설치한다)으로 두자. 직전 공유기 설치점과 현재 지점의 거리가 dist 이상이라면 공유기를 설치할 수 있다. 그렇지 않으면 다음 지점으로 이동한다.
• 만약 공유기를 최대한 설치했을 때, 그 값이 C 이상이라면 이 최소 인접 거리는 정답 후보가 될 수 있다. 또한, 우리는 최대 거리를 구하고자 하므로, 탐색 시작점 start를 dist + 1로 업데이트한다.
• 위에 해당하지 않는다면 end를 dist - 1로 업데이트한다. 이를 start < end 조건문 내에서 반복하도록 한다.

 

 

풀이 코드

import sys
input = sys.stdin.readline

N, C = map(int, input().split())
house_list = sorted([int(input()) for _ in range(N)])
start, end = 1, house_list[-1] - house_list[0]
answer = 0
while start <= end :
  mid = (start + end) // 2
  prev, cnt = house_list[0], 1
  for i in range(1, N) :
    if house_list[i] - prev >= mid :
      cnt += 1
      prev = house_list[i]
  if cnt >= C :
    answer = max(answer, mid)
    start = mid + 1
  else :
    end = mid - 1

print(answer)

풀이 완료!