[백준] 1477 휴게소 세우기

새로운 휴게소를 기존 휴게소 사이에 건설할 때 휴게소 사이의 거리가 가장 멀 때의 최솟 값을 구하여라

풀이방법

새로운 휴게소를 지을 때 짓기 전에 미리 가장 멀 때의 값을 가정합니다. 그리고 휴게소를 해당 간격에 따라서 설치를 합니다. 만약 설치한 휴게소의 갯수가 새롭게 설치할 수 있는 휴게소의 갯수를 넘어서면 가정한 거리를 더 길게하여서 다시 설치해 봅니다. 이러한 과정을 거쳐서 문제의 답을 구합니다.

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

int N, M, L;

int main() {
  cin >> N >> M >> L;
  int answer;
  vector<int> hugaeso_group;

  for (int i = 0; i < N; i++) {
    int hugaeso;
    cin >> hugaeso;
    hugaeso_group.push_back(hugaeso);
  }
  sort(hugaeso_group.begin(), hugaeso_group.end());

  int m, h, l;

  l = 0;
  h = L;
  m = (l + h) / 2;

  while (l + 1 < h) {
    m = (l + h) / 2;
    int cnt = 0, prev_hugaeso = 0;

    for (int i = 0; i < N; i++) {
      cnt += (hugaeso_group[i] - prev_hugaeso) % m == 0
                 ? (hugaeso_group[i] - prev_hugaeso) / m - 1
                 : (hugaeso_group[i] - prev_hugaeso) / m;
      prev_hugaeso = hugaeso_group[i];
    }

    cnt += (L - hugaeso_group[N - 1]) % m == 0
               ? (L - hugaeso_group[N - 1]) / m - 1
               : (L - hugaeso_group[N - 1]) / m;

    if (cnt <= M) {
      answer = m;
      h = m;
    } else {
      l = m;
    }
  }
  cout << answer;
}

[백준] 1477 휴게소 세우기

Abstract

[백준] 1477번 휴게소 세우기

알고리즘 유형

문제 이해

풀이방법