[백준 1477] 휴게소 세우기

www.acmicpc.net/problem/1477

1477번: 휴게소 세우기

이분탐색이라는 걸 알았는데도 생각해내는데 오래걸렸다..ㅠㅠ

1. 거리를 기준으로 삼아서 mid

2. 거리가 조건에 충족하는지 여부에 따라 (cnt==m?)

3. start, end범위가 달라진다.

 

거리 계산을 쉽게하기 위해 0과 l-1(고속도로 끝자락엔 휴게소 세울 수 없음)을 넣어주고 소팅을 해주었다.

모든 거리 차에 대해 mid 이하를 갖는 휴게소를 총 몇 개 세울 수 있는 지 계산한다.

이 때 거리차를 계산할 때(v[i] - v[i-1]) 1을 빼줘야 한다.

200과 701 사이에 거리가 250 이하가 되도록 휴게소를 세운다고 해보자.

701-200 = 501

501 / 250 = 2

200 450 700 701 -> 400과 700 2개가 추가된 것을 확인할 수 있다.

하지만 200과 700사이로 바꾼다면?

500/250 = 2

200 450 700 -> 2 이지만 450하나만 있어도 됨을 확인할 수 있다.

 

만약 cnt>m이라면 주어진 거리가 너무 작다는 의미이다.

거리를 늘려야 하므로 start = mid+1을 해준다.

 

만약  cnt< m이라면 end = mid-1이다..

 

만약 cnt=m이라면 정답의 가능성이 있지만 그 중에서 최솟값을 찾아야 하므로 end = mid로 설정한다.

 

그래서 cnt<=m인 경우 end = mid를 해주고 end를 리턴한다.

#include <stdio.h>
#include <algorithm>
#include <vector>

using namespace std;

int n, m, l;
vector<int> v;
int main(void)
{
  scanf("%d%d%d", &n, &m, &l);
  v.push_back(0);
  v.push_back(l - 1);
  for (int i = 1; i <= n; i++)
  {
    int tmp;
    scanf("%d", &tmp);
    v.push_back(tmp);
  }

  sort(v.begin(), v.end());

  int start = 0, end = l;

  while (start < end)
  {

    int mid = (start + end) / 2;
    int cnt = 0;
    for (int i = 1; i < v.size(); i++)
    {
      cnt += (v[i] - v[i - 1] - 1) / mid;
    }

    if (cnt > m)
    {
      start = mid + 1;
    }
    else
    {
      end = mid;
    }
  }

  printf("%d\n", end);

  return 0;
}