오늘의 학습 키워드

• 이분탐색

[백준] 공유기 설치 - 2110

• [백준] 공유기 설치 - 2110
• Gold IV
• 풀이시간: 40m
• C++ 풀이

문제해설

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

이 문제에서 이분탐색의 대상은 두 공유기 사이의 최소 거리입니다.
탐색 대상인 최소 거리 mid를 기준으로, 두 집 사이의 거리가 작으면 공유기를 설치하지 않습니다. 반대로, 거리가 mid 이상이면 조건을 만족하므로 공유기를 설치하게 됩니다.

• 출발점(현재 위치): 집들의 좌표가 정렬되어 있다고 가정할 때, 가장 작은 x좌표를 가진 집에서 시작합니다.
• 공유기 설치 조건:
  • 만약 현재 집과 다음 집 사이의 거리가 mid보다 크거나 같다면, 조건을 만족하므로 해당 집에 공유기를 설치합니다.
  • 이때 공유기를 설치하면, 현재 위치를 해당 집의 x좌표로 갱신합니다.
  • 반대로, 두 집 사이의 거리가 mid보다 작으면 조건에 맞지 않으므로 공유기를 설치하지 않습니다.

이렇게 진행하면서 공유기를 설치할 때마다 설치 개수를 카운트하게 되고, 최종적으로 구한 공유기 설치 개수와 주어진 공유기 개수 C를 비교하여 이분탐색을 진행합니다.

설치한 공유기 개수 cnt >= 주어진 C
cnt가 C보다 큰 경우 공유기 설치를 줄여야 한다는 뜻이고, 두 공유기 사이의 최소 거리를 늘려야함을 의미합니다.
문제의 목표가 가장 인접한 두 공유기 사이의 거리를 최대로 하는 것이기 때문에, 조건에 등호(>=)를 붙여주면 최적의 해를 찾을 수 있습니다.

접근법: 이분탐색

#include <bits/stdc++.h>

using namespace std;

int main() {
  int N, C, dist[200001];

  cin >> N >> C;
  for (int i = 0; i < N; i++){
    cin >> dist[i];
  }

  sort(dist, dist + N);
  
  int st = 1, ed = dist[N - 1] - dist[0], ans = 0;

  while (st <= ed) {
    long long mid = (st + ed) / 2;
    int cnt = 1;
    int cur = dist[0];

    for (int i = 1 ;i < N; i++){
      if (dist[i] - cur >= mid) {
        cnt++;
        cur = dist[i];
      }
    }

    if (cnt >= C) {
      st = mid + 1;
      ans = mid;
    }
    else {
      ed = mid - 1;
    }
  }

  cout << ans << "\n";
}

오늘의 회고

이분탐색 문제를 오랜만에 풀어보니, 어떤 것을 이분탐색의 대상으로 삼아야 할지 결정하지 못했습니다. 한 30분 넘게 머리를 굴려봤지만, 문제의 파훼법을 제대로 모르겠어서 결국 풀이법을 참고했습니다. 스스로 푼 게 아니기에, 아쉬운 마음이 남아 비슷한 유형의 문제인 [level 4] 징검다리 - 43236를 이어서 풀어보았습니다. 이제 비슷한 유형은 더 이상 틀리면 안 되겠죠?