[백준] 2110 공유기 설치

March 23, 2021 ( last updated : March 23, 2021 )
이분탐색 알고리즘 algorithm

https://github.com/sneakstarberry/

Abstract

[백준] 2110번 공유기 설치

[백준] 2110번 공유기 설치

백준 2110번

알고리즘 유형

문제 이해

공유기 끼리 가장 가까운 것의 거리가 최대한 길게하면된다.

풀이 방법

공유기 끼리 가장 거리가 가장 멀려면 어떻게 해야할까? 숫자를 세보면 된다. 어떤 숫자를 세냐면 특정 거리보다 공유기 사이의 거리가 먼 경우의 수를 세보면된다. 이 중 어떤 특정 거리의 경우의 수는 공유기의 숫자와 같을 것이다. 그렇다면 그 거리가 정답이다.

그렇다면 특정 거리보다 공유기 사이의 거리가 먼 경우의 수는 어떻게 세야지 정확한 숫자가 나올 것인가?

이전 공유기 설치 집과 현재 집의 거리를 잰다. 둘 사이의 거리가 특정거리보다 멀다면 그 곳에 공유기를 설치하고 그 곳을 다시 이전 공유기 설치 집으로 지정하는 것이다. 이를 수식으로 표현하면 이렇다.

house_x_group[i] - prev >= distance
house_x_group[i] = 현재 집;
prev = 이전 공유기 설치 집;
distance = 특정 거리

이제 전체 코드를 보면된다.

#include <algorithm>
#include <iostream>

using namespace std;
#define MAX 200111

int N, C;

void solve();
int needed_wifi_counter(int distance, int house_x_group[MAX]);

int main() {
  cin >> N >> C;

  solve();

  return 0;
}

void solve() {
  int house_x_group[MAX];

  for (int i = 0; i < N; i++) {
    cin >> house_x_group[i];
  }
  sort(house_x_group, house_x_group + N);
  int h, l, m, needed_wifi_cnt, ans = 1;
  h = house_x_group[N-1] + 1;
  l = 0;

  while (l + 1 < h) {
    m = (h + l) / 2;

    needed_wifi_cnt = needed_wifi_counter(m, house_x_group);

    if (needed_wifi_cnt < C) {
      h = m;
    } else {
      ans = m;
      l = m;
    }
  }
  cout << ans;
}

int needed_wifi_counter(int distance, int house_x_group[MAX]) {
  int cnt = 1;
  int prev = house_x_group[0];
  for (int i = 1; i < N; i++) {
    if (house_x_group[i] - prev >= distance) {
      cnt++;
      prev = house_x_group[i];
    }
  }

  return cnt;
}

Originally published March 23, 2021
Latest update March 23, 2021

Related posts :

{# #}