44강

💎

• 일직선 수직선 상에 말을 배열을 할 것인데, x좌표와 말의 수를 입력을 받을 것이다. 이런 상황에서 말 사이의 간격중 최소값이 최대일때의 값은 무엇인가?

• 접근법 :
  1) 정답이 될 수 있는 수는 1부터 x좌표의 최댓값 사이의 값이다.
  2) 이 수 중에서 하나의 수를 골라서 답인지 아닌지를 확인하므로, 이분검색 결정알고리즘을 이용한다.
  3) 그러기 위해서 입력받은 배열을 먼저 정렬을 해준다.
  4) 이 문제에서 많은 말을 정렬하기 위해서는 앞쪽 배열부터 채우게 되면 많은 말을 배열 할 수가 있다.
  5) 따라서 mid 값 즉 값이 될 값에 대하여 배열의 첫번째 인덱스와 그후에 나오는 인덱스 값의 절대값 차를 구하여 만약에 이 값이 mid보다 크거나 같다면 카운터의 값을 하나 올려준다. 그리고 이렇게 되면 첫번째 인덱스에 대한 짝을 찾은 것이기 때문에 첫번째 인덱스를 고른 상태가 된다. 첫번째 인덱스를 골랐기 때문에 두번째 고른 인덱스 앞에 있는 숫자들은 고를수가 없다. 따라서 이번에는 두번째로 고른 인덱스와 해당 인덱스 뒤에있는 인덱스들과의 절댓값 차를 구하여 mid의 값과 비교를하고 cnt의 값을 바꿔준다.
  6) 이렇게 해주었다면 이제 그 결과값 cnt 값을 return 해주고 그 값과 말의 수들을 비교하여 말의 수와 같거나 크면 해당 값은 조건을 만족하는 값이므로 mid는 결과가 될수 있다. 그 이후에는 값이 더 클 수도 있으므로 lt=mid+1 의 값으로 다시 값을 확인해본다.
  7) 말의 수보다 작다면 rt=mid-1로 값을 다시 확인한다.

• 소스코드

#include <stdio.h>
#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;
int n;
vector<int> v;
int check(int mid){
	int cnt=1,cur=v[0];
	for(int i=1;i<n;i++){
		if(v[i]-cur >= mid){
			cnt++;
			cur=v[i];
		}
	}
	return cnt;
}


int main(){
	//freopen("input.txt", "rt", stdin);
	int c,lt=1,rt,res,mid;
	scanf("%d %d",&n,&c);
	v.resize(n);
	for(int i=0;i<n;i++){
		scanf("%d",&v[i]);
	}
	sort(v.begin(),v.end());
	rt=v[n-1];
	while(lt <= rt){
		mid=(lt+rt)/2;
		if(check(mid) >= c){
			res=mid;
			lt=mid+1;
		}
		else{
			rt=mid-1;
		}
	}
	printf("%d",res);
	
	
		
	return 0;
}