마구간 정하기(이분검색, 결정 알고리즘) / c / 제한시간 없음

▣ 문제

- N개의 마구간이 1차원 수직선상에 있습니다. 각 마구간은 x1, x2, x3, ......, xN의 좌표를 가 지며, 마구간간에 좌표가 중복되는 일은 없습니다. 현수는 C마리의 말을 가지고 있는데, 이 말들은 서로 가까이 있는 것을 좋아하지 않습니다. 각 마구간에는 한 마리의 말만 넣을 수 있고, 가장 가까운 두 말의 거리가 최대가 되게 말을 마구간에 배치하고 싶습니다. C마리의 말을 N개의 마구간에 배치했을 때 가장 가까운 두 말의 거리가 최대가 되는 그 최대 값을 출력하는 프로그램을 작성하세요.

 

▣ 입력설명

- 첫 줄에 자연수 N(3<=N<=200,000)과 C(2<=C<=N)이 공백을 사이에 두고 주어집니다. 둘째 줄부터 N개의 줄에 걸쳐 마구간의 좌표 xi(0<=xi<=1,000,000,000)가 한 줄에 하나씩 주어집니다.

 

▣ 출력설명

- 첫 줄에 가장 가까운 두 말의 최대 거리를 출력하세요.

 

▣ 입력 예시

5 3 1 2 8 4 9

 

▣ 출력 예시

3

 

<내 코드>

#pragma warning(disable:4996)
#include<stdio.h>
#include<stdlib.h>

int stall[200001];
int c;
int cnt;
int n, i;

int compare(const void* n1, const void* n2) {
	if (*(int*)n1 > * (int*)n2)
		return 1;
	else if (*(int*)n1 < *(int*)n2)
		return -1;
	else return 0;
}

int check(int mid) {
	int i;
	int temp;
	cnt = 1;
	temp = stall[1];
	for (i = 2; i <= n; i++) {
		if (stall[i] - temp >= mid) {
			cnt++;
			temp = stall[i];
		}
	}
	if (cnt < c) return 0;
	else return 1;

}

int main() {
	int lt = 1, rt, mid;
	int ans = 0;
	scanf("%d %d", &n, &c);
	for (i = 1; i <= n; i++) {
		scanf("%d", &stall[i]);
	}
	qsort(stall, n, sizeof(int), compare);
	rt = stall[n];
	while (lt <= rt) {
		mid = (rt + lt) / 2;
		if(check(mid)){
			ans = mid;
			lt = mid + 1;
		}
		else {
			rt = mid - 1;
		}
	}
	printf("%d\n", ans);
	return 0;
}

지난번에 풀어본 결정 알고리즘과 매우 흡사한 형태로 접근해봤다.

 

우선, 마구간의 좌표를 qsort를 이용해 정렬을 시키고 check 함수를 통해서 mid값으로 말을 마구간에 넣을수 있는지 판별했다.

 

check 함수의 원리는 다음과 같다

 

1                  2                                             4                                                               8             9   

---

와 같이 마구간이 있다면 temp는 말이 들어갈 수 있는 자리를 나타낸다. stall[i] - temp >= mid 을 통해서 다음 마구간의 위치와 현재 말이 들어가있는 자리의 차가 mid 보다 작으면 말의 다음 위치를 바꿔주고 cnt++을 해주었다.

 

1 temp=stall[1]  2                                             4 if(stall[i] - temp >= mid) cnt++;temp=stall[4]   8             9 

---

이렇게 for문이 끝나고 cnt가 c보다 작으면 그 mid값으로는 c마리의 말을 놓을수 없기때문에 return 0을 해주었다.

 

나머지는 이분검색을 통해서 mid값을 찾는 방식이다.

 

.

 

뮤직비디오 문제를 보고 다시 하면 할만한듯