[알고리즘] C++ 백준 1477 휴게소 세우기

백준 1477

https://www.acmicpc.net/problem/1477

1477번: 휴게소 세우기

풀이 전 나의 생각

고속도로에 있는 휴게소의 위치 N 개가 주어진다. 

이때 휴게소 M 개를 추가적으로 설치할 때 휴게소가 없는 구간의 길이의

최댓값을 최소로 하는 값을 구해야 한다.

 

조건

- 0 ≤ N ≤ 50

- 1 ≤ M ≤ 100

- 100 ≤ L ≤ 1,000

- 1 ≤ 휴게소의 위치 ≤ L-1

- N+M < L

- 모든 휴게소의 위치는 중복되지 않음

- 입력으로 주어지는 모든 수는 정수

 

과정

- N, M, L, 휴게소간의 거리의 누적합 등 int 범위를 넘지 않을 정도의 범위가 주어졌기 때문에

데이터 타입을 int로 설정한다.

 

- 구간의 길이를 최소로하는 값을 1부터 차례대로 탐색을 하며 N개 만큼 계산 한다면

아무리 범위가 적어도 엄청난 계산 횟수로 인하여 비효율적일 것이다.

따라서 휴게소간의 거리를 구하는 부분을 이분 탐색을 사용하여 탐색을 진행한다.  

 

- 휴게소의 위치를 구해야 하기 때문에 이분 탐색의 시작점과 끝점을 

조건에 나와있는 1 ≤ 휴게소의 위치 ≤ L-1 을 참고하여 설정한다.

 

- 휴게소 간의 거리가 최대가 되면서 최소가 된다는 의미는

그만큼 균형있는 거리의 값을 구해야 한다는 것이다.

따라서 휴게소 간의 거리에 설정 거리만큼 휴게소를 몇개 설치할지 구하고

만약 휴게소 설치 개수가 현재 설정된 M 개보다 많다면 설정 거리를 늘려주고

적다면 설정 거리를 줄여준다.

 

1. 휴게소 간의 거리를 구하기 위해 시작과 끝을 설정해준다.

vector<int>location;

location.push_back(0);
location.push_back(L);

예를 들어 80, 100, 120의 휴게소 위치가 주어지고 고속도로의 길이가 150일 때

0 ~ 80 사이의 거리와 120 ~ 150사이의 거리를 구해야 하기 때문이다.

 

2. 휴게소를 설치할 거리를 이분 탐색을 진행하기 위해 시작과 끝을 설정해준다.

int start = 1;
int end = L - 1;

조건 : - 1 ≤ 휴게소의 위치 ≤ L-1

 

3. 휴게소 간의 거리에 휴게소를 설치할 간격을 구하고 몇개를 설치할 수 있는지 구한다.

while (start <= end)
	{
		int mid = (start + end) / 2;
		int sum = 0;

		for (int i = 1; i < location.size(); i++)
		{
			int dist = location[i] - location[i - 1];
			int cnt = dist / mid;

			if (dist % mid == 0)
			{
				cnt -= 1;
			}

			sum += cnt;
		}
		....

예를 들어 휴게소 0과 80의 거리인 80에 휴게소를 설치할 간격 20이 있다고 하면

80 / 20 = 4 즉, 4개의 휴게소를 20의 간격으로 설치할 수 있다.

 

하지만 나누어 떨어진다는 것은 휴게소의 위치가 겹쳤다는 의미기 때문에 

설치한 개수에서 하나를 빼준다.

 

그렇게 구한 휴게소의 설치 개수의 누적합을 구한다.

 

4. 휴게소의 최종 설치 개수를 휴게소 M 개의 기준에 따라 탐색 방향을 설정한다.

if (sum > M)
{
	start = mid + 1;
}
else
{
	end = mid - 1;
	ans = min(ans, mid);
}

휴게소의 최종 설치 개수를 구한 누적합인 sum을 기준으로

현재 설정된 목표 휴게소의 설치 개수 M보다 크다면

휴게소 설치 간격이 작다는 의미기 때문에 간격을 늘려준다.

 

반대로 M보다 작다면 휴게소 설치 간격이 크다는 의미기 때문에

간격을 줄여주며 구하고자 하는 휴게소간의 거리 중 최대가 되면서 최소가 되는

값을 갱신시켜준다.

풀이

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
#include <queue>
#include <string.h>
#include <limits.h>
#include <cstdio>

using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int N, M, L, ans = 1000;
	cin >> N >> M >> L;

	vector<int>location;

	location.push_back(0);
	location.push_back(L);

	for (int i = 0; i < N; i++)
	{
		int info;
		cin >> info;
		location.push_back(info);
	}

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

	int start = 1;
	int end = L - 1;

	while (start <= end)
	{
		int mid = (start + end) / 2;
		int sum = 0;

		for (int i = 1; i < location.size(); i++)
		{
			int dist = location[i] - location[i - 1];
			int cnt = dist / mid;

			if (dist % mid == 0)
			{
				cnt -= 1;
			}

			sum += cnt;
		}

		if (sum > M)
		{
			start = mid + 1;
		}
		else
		{
			end = mid - 1;
			ans = min(ans, mid);
		}
	}

	cout << ans;
}