백준 2110 공유기 설치

 

공유기 설치

 

 

이분 탐색을 이용하여야 한다는 생각을 가지고도 어떻게 문제에 접근해야할지 감이 오지 않아서 블로그 글들을 조금 참고하여 코드를 짰다!...

 

1. 맨 처음 집에는 무조건 공유기가 설치된다.

2. 왼쪽에서 오른쪽 방향으로 공유기가 설치된다. 

3. 공유기의 설치 가능한 최소 거리는 1이다.

 

이 세가지를 중심으로 코드를 짰다.

int wifi(int start, int end) {
	int result = 0;//가장 긴 거리 중 최솟값
	while (start <= end) {
	
		int mid = (start + end) / 2;
		int cnt = 1;
		int prev_house = house[0];
		for (int i = 1; i < n; i++) {
			if (house[i] - prev_house >= mid) {
				cnt++;
				prev_house = house[i];
			}
		}
		if (cnt >= w) {
			result = mid;
			start= mid+1;
		}
		//거리를 크게해서 조금 설치 가능;
		if (cnt < w) {
			end = mid-1;
		}
		//거리를 좁혀서 더 설치해야함
	}
	return result;
}

result 에 가장 긴 거리중 최소 거리를 저장하여 반환해 주었다. 이진 탐색을 이용하였고 mid 보다 더 멀리 떨언 거리에만 공유기가 설치 되도록 하였다. 

cnt에 설치된 공유기의 개수를 세주었는데, 설치된 공유기의 개수가 w(설치해야하는 공유기의 수)보다 크거나 같으면 길이를 늘려서 더 넓은 구역으로 공유가 설치가 가능하다는 의미이니 mid값을 증가시키기 위해 start의 값을 mid+1로 할당해준다. cnt가 w보다 작은 값이라면 공유기 설치가 더 이루어져야 하므로 mid를 줄여 좀 더 촘촘하게 공유기를 설치해야 해 end에 mid -1의 값을 주었다. 

이 때 공유기의 수가 더 작은 경우에는 최소 거리가 될 수 없다. 그래서 공유기의 수가 더 많거나 같은 경우에만 result값을 업데이트 시켜줬다. 

 

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n>>w;
	int min = 1000000000;
	int max = 0;
	for (int i = 0; i < n; i++) {
		int h;
		cin >> h;
		house.push_back(h);
	}
	sort(house.begin(), house.end());

	min = wifi(1,house[n-1]-house[0]);

	cout << min;
	return 0;
}

 

 

메인 함수에서는 house 벡터의 집의 위치를 저장하고 정렬한다. 

 

공유기 설치 최소 길이는 1이고 최대거리는 마지막 집과 첫번째 집의 차이이므로 이를 wifi 함수에 인수로 준다.