공유기 설치

[Gold IV] 공유기 설치 - 2110

문제 링크

성능 요약

메모리: 2684 KB, 시간: 52 ms

분류

이분 탐색, 매개 변수 탐색

제출 일자

2023년 12월 27일 11:34:03

문제 설명

도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x₁, …, x_N이고, 집 여러 개가 같은 좌표를 가지는 일은 없다.

도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다.

C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오.

입력

첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 x_i (0 ≤ x_i ≤ 1,000,000,000)가 한 줄에 하나씩 주어진다.

출력

첫째 줄에 가장 인접한 두 공유기 사이의 최대 거리를 출력한다.

TIL

• 문제 상황을 이해하여, 알맞는 결정함수를 설계하자.
  특히 예제 케이스를 깊게 이해하여야 한다.

FeedBack

• parametric search에 대한 문제를 계속 풀다보니 정말 쉬워졌다.
  다만 문제 상황에 따른 결정함수를 초반에 잘못 설계하여 거기서 시간이 좀 소비되었다. 예제 케이스는 100% 이해하고 접근하자.
• 동적 메모리 할당 해제해주자.

같은 유형에 대해 문제를 많이 풀다보니 Gold 문제라고 안 느껴진다.
그만큼 쉽게 느껴지고 내 실력이 올라오는 것이 느껴진다.
하나의 알고리즘을 설정하고, 이에 대한 많은 알고리즘을 푸는 방법이 실력 향상에 있어 많은 도움이 된다.

내 접근

parametric search로 바로 접근. 전체적인 틀도 바로바로 만들었고 5분컷 낼 것같았지만.. 결정 함수 설계 미스로 인해 시간이 조금 소비되었다.

내 코드

#include <stdio.h>
#include <stdbool.h>
#define MAX 1000000000
int compare(const void* a, const void* b);


int main() {

	//input
	int n, limit;
	scanf("%d %d", &n,&limit);
	int* homes = (int*)malloc(sizeof(int) * n);
	for (size_t i = 0; i < n; i++)
		scanf("%d", &homes[i]);

	qsort(homes, n, sizeof(int), compare);

	int low = 1, high = MAX;
	while (low <= high) {
		int mid = low + (high - low) / 2;
		int usedRouter = 0;
		int nextPoint = 0;
		for (size_t i = 0; i < n; i++) {
			if (homes[i] >= nextPoint) {
				usedRouter++;
				nextPoint =homes[i]+ mid;
			}
		}
		
		if (usedRouter>= limit) low = mid + 1;
		else high = mid - 1;
	}
	printf("%d", high);
	free(homes);
	return 0;
}

int compare(const void* a, const void* b)
{
	if (*(int*)a > *(int*)b)

		return 1;

	else if (*(int*)a < *(int*)b)

		return -1;

	else

		return 0;
}