[BOJ] 2110 - 공유기 설치

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

BOJ - 공유기 설치

문제 유형: 이진 탐색, 매개 변수 탐색(parametric search)

문제 난이도: Gold IV

시간 제한: 2초

메모리 제한: 128MB

 

문제

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

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

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

 

입력

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

 

출력

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

 

풀이

최초의 최소 바운더리와 최대 바운더리를 각각 1, arr[n-1] - arr[0]으로 한다.

lo가 hi보다 작거나 같은 동안,

 각 공유기들 사이의 최소 거리를 보장할 숫자 mid를 (lo + hi)/2로 지정하고,

 순차적으로 배열을 순회하면서 c개 설치가능한지 조사한다.

  가능하다면, 우선 정답값을 업데이트하고, 거리를 더 키워보기 위해서 lo = mid+1로 업데이트한다.

  아니면, 거리를 더 줄여야 한다. hi = mid-1로 업데이트한다.

 

코드

C++

#include <bits/stdc++.h>

using namespace std;

int main(int argc, char *argv[]) {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  int n, c;
  cin >> n >> c;
  vector<int> arr(n);
  for (int &x : arr) {
    cin >> x;
  }

  sort(arr.begin(), arr.end());
  int lo = 1, hi = arr.back() - arr[0];

  int ans = 0;

  while (lo <= hi) {
    int mid = (lo + hi) / 2;
    int last = arr[0];
    int cnt = 1;
    bool flag = false;
    for (int i = 1; i < n; ++i) {
      if (arr[i] - last >= mid) {
        last = arr[i];
        cnt++;
        if (cnt == c) {
          flag = true;
          break;
        }
      }
    }

    if (flag) {
      ans = mid;
      lo = mid + 1;
    } else {
      hi = mid - 1;
    }
  }
  cout << ans << "\n";

  return 0;
}

 

Go

package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
)

func main() {
	reader := bufio.NewReader(os.Stdin)
	writer := bufio.NewWriter(os.Stdout)
	defer writer.Flush()

	var n, c int32
	fmt.Fscan(reader, &n, &c)
	arr := make([]int32, n)
	for i := int32(0); i < n; i++ {
		fmt.Fscan(reader, &arr[i])
	}
	sort.Slice(arr, func(i, j int) bool {
		return arr[i] < arr[j]
	})

	lo := int32(1)
	hi := int32(arr[n-1] - arr[0])
	for lo <= hi {
		mid := (lo + hi) / 2
		flag := false
		last := int32(arr[0])
		cnt := int32(1)
		for i := int32(1); i < n; i++ {
			if arr[i]-last >= mid {
				last = arr[i]
				cnt++
				if cnt == c {
					flag = true
					break
				}
			}
		}
		if flag {
			lo = mid + 1
		} else {
			hi = mid - 1
		}
	}

	fmt.Fprintln(writer, lo-1)
}