2110 공유기

2110 공유기 - 백준

• Problem Define
  N개의 집이 수직선 위에 겹치지 않는 위치에 있다. 공유기 C개 각 집 위에 설치하려고 한다. 이때 가장 인접한 두 공유기 사이의 거리를 가능한 크게 설치할 때의 거리를 구하여라.

• Basic Idea
  공유기 사이의 가능한 최대 거리는 (가장 멀리 있는 집의 위치 - 가장 가까이 있는 집의 위치)/공유기의 수이다.
  공유기 사이의 가능한 최소 거리는 집의 좌표 중 가장 짧은 거리이다.
  맨 처음 집에 라우터를 설치하는 것이 두 공유기 사이의 거리를 크게 할 가능성을 높인다.
  다른 공유기의 거리는 인접한 두 공유기 사이의 거리보다 더 커야 한다.

• What To Do?
  1. 집을 거리에 따라 sorting 한다.
  2. 공유기 사이의 최대 거리와 최소 거리 사이의 모든 공유기가 설치될 수 있는 최대 거리를 구한다.

• How To Do?
  수직선 상에 N개의 집이 존재한다.
  1. Quick Sort를 통해 log N 만에 sorting한다.
  2. Binary search를 통해 최적의 공유기 거리를 구한다.
  1) 공유기 거리 k에 모든 공유기가 설치될 수 있다면 공유기의 거리를 k보다 넓힌다.
  2) 공유기 거리 n에 모든 공유기가 설치될 수 없다면 공유기의 거리를 k보다 좁힌다.

• Time Complexity
  - Time Complexity : T(N) = θ(N log N) <- heap sort + binary search*N

  • Space Complexity : θ(N)