Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 푸는 주유소 간 최대 거리 최소화 문제 (이진 탐색 활용)

수평선 위에 여러 개의 주유소가 있다고 가정해 봅시다. 이 수직선에는 stations[0], stations[1], ..., stations[N-1] 위치에 주유소가 배치되어 있으며, N은 배열의 크기입니다. 여기에 K개의 새로운 주유소를 추가하여, 인접한 주유소 사이 거리 중 최댓값인 D를 최소화하려고 합니다. 우리가 구해야 할 것은 가능한 D의 최솟값입니다.

문제 예시

예를 들어, 입력이 다음과 같다고 해보겠습니다:

  • stations = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
  • K = 9

이 경우 출력은 0.5가 됩니다. 기존 주유소는 1씩 떨어져 있고, 9개를 추가하면 총 18개의 구간이 생기므로 전체 길이(10 - 1 = 9)를 18개 구간으로 나눈 0.5가 최대 거리의 최솟값이 되기 때문입니다.

해결 접근 방식: 매개변수 탐색 (이진 탐색)

이 문제는 답이 실수 범위에 있으므로 일반적인 정수 이진 탐색 대신 실수 값에 대한 이진 탐색(매개변수 탐색)을 사용합니다. 핵심 아이디어는 다음과 같습니다:

  • 어떤 거리 x가 주어졌을 때, 모든 인접 구간의 거리가 x 이하가 되도록 하려면 몇 개의 주유소가 추가로 필요한지 계산할 수 있습니다.
  • 필요한 주유소 개수가 K 이하라면, x는 유효한 후보입니다. 따라서 더 작은 값을 탐색합니다.
  • K보다 많이 필요하다면, x는 너무 작으므로 더 큰 값을 탐색합니다.

특정 구간의 길이가 L이고 허용 거리가 x일 때, 그 구간에 필요한 추가 주유소 수는 ceil(L / x) - 1입니다. 예를 들어 구간 길이가 3이고 x가 1이라면, ceil(3/1) - 1 = 2개의 주유소가 추가로 필요합니다.

ok() 함수 정의

  • x와 배열 v를 받는 ok(x, v) 함수를 정의합니다.
  • ret := 0으로 초기화합니다.
  • i := 0부터 시작하여 i < v.size() 동안 i를 1씩 증가시키며 반복합니다:
    • ret := ret + ceil((v[i+1] - v[i]) / x) - 1
  • ret을 반환합니다.

메인 로직 (minmaxGasDist)

  • low := 0으로 초기화합니다.
  • n := s의 크기
  • high := s[n-1] - s[0] (전체 구간 길이)
  • high - low >= 1e-6 동안 반복합니다 (충분한 정밀도 확보):
    • mid := (low + high) / 2.0
    • x := ok(mid, s) — mid 거리에서 필요한 추가 주유소 개수
    • 만약 x > K이면 low := mid (거리를 늘려야 함)
    • 그렇지 않으면 high := mid (거리를 줄일 수 있음)
  • high를 반환합니다.

C++ 구현 코드

아래는 전체 구현 예시입니다:

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int ok(double x, vector <int>& v){
      int ret = 0;
      for (int i = 0; i < v.size() - 1; i++) {
         ret += ceil((v[i + 1] - v[i]) / x) - 1;
      }
      return ret;
   }
   double minmaxGasDist(vector<int>& s, int K) {
      double low = 0;
      int n = s.size();
      double high = s[n - 1] - s[0];
      while (high - low >= 1e-6) {
         double mid = (low + high) / 2.0;
         int x = ok(mid, s);
         if (x > K) {
            low = mid;
         }
         else {
            high = mid;
         }
      }
      return high;
   }
};
main(){
   Solution ob;
   vector<int> v = {1,2,3,4,5,6,7,8,9,10};
   cout << (ob.minmaxGasDist(v, 9));
}

입력

{1,2,3,4,5,6,7,8,9,10}, 9

출력

0.5

시간 복잡도 분석

이진 탐색의 범위는 [0, 최대 구간 길이]이며, 오차 허용 범위가 1e-6이므로 약 log₂(범위 / 1e-6)번의 반복이 필요합니다. 각 반복마다 ok() 함수는 O(N) 시간에 실행되므로, 전체 시간 복잡도는 O(N × log(maxDist / ε))입니다. 여기서 N은 주유소 개수, maxDist는 초기 최대 거리, ε은 오차 허용값입니다.