#include <stdio.h>
#include <algorithm>
using namespace std;
int N;
int Count(int size, int xi[]){//dvd개수
int p = xi[1],i,cnt=1;
for(i = 2; i <= N; i++){
//뒤에 값들과 빼보다가
//두 마굿간의 길이가 정답보다 크거나 같다면
//말을 배치할 수 있음
//그 자리에서 다음 마굿간과의 거리를 재서 크거나 같으면 말을 배치함
//만약 정답이 3(mid == 3)이라면
//마굿간 두 쌍의 거리가 둘 다 3보다 커야지
//두 마굿간 중 가까운 마굿간 쌍의 거리가 3으로 설명할 수 있으므로
if(xi[i] - p >= size){
cnt++;
p = xi[i];
}
}
return cnt; //배치한 말의 수
}
int main() {
int C,lt=1,rt,mid,i,res;
scanf("%d %d",&N,&C);
int *xi = new int[N+1];
for(i = 1; i <= N; i++){
scanf("%d",&xi[i]);
}
sort(xi+1, xi + (N+1));
rt = xi[N];
while(lt <= rt){
mid = (lt+rt)/2; //정답 하나 뽑아보기
if(Count(mid,xi) >= C){//이거 정답 맞아? 넘겨줌
// cnt가 3보다 작으면 말 3마리 배치를 못한다는 거니까 오답
// 첫 반복때 Mid가 5인데 그럼 오답임.
res = mid;
lt = mid+1;
}
else rt = mid-1;
}
printf("%d\n",res);
delete[] xi;
return 0;
}
뮤직비디오 문제와 푸는 방식이 동일하다
1~8 사이에 정답 있을 것이라고 가정하고 말 세마리를 배치할 수 있는지 이분검색을 시작한다.
만약 정답(가장 가까운 두 말의 최대거리)을 4(mid)라고 한다면 말을 두마리밖에 배치하지 못하기 때문에 rt를 줄인다. 1~3
만약 정답을 2(mid)라고 한다면 말을 세 마리 배치할 수 있기 때문에 정답이다. 하지만 더 좋은 정답을 찾기위해 이분탐색은 계속한다
만약 정답을 3(mid)라고 한다면 말을 세 마리 배치할 수 있기 때문에 정답이다. 2와 3이 있지만 최대거리를 구하기 때문에 3이 정답이 된다.
*주의 이분 검색을 통해 정답을 2로 정해놓고 Count함수로 보내게 되면, 1 - 4 - 8 에 말을 배치하여 끝내게된다. 무조건 크거나 같으면 cnt++을 하기 때문이다. 정답은 2로 정해놓고 Count로 보냈는데 가장 가까운 말의 거리는 3이된다. 이러면 올바르게 동작했다고 볼 수 있나? : YES 정답을 2로 정해놓고 보내긴 했으나, 실제로는 1 - 4 - 8로도 배치가 가능하다라는 방안을 리턴받게 되는 것이다. 그럼 결국 다음 단계에서 2보다 더 좋은 답안인 3을 얻게 되는 것이다.
결국 Count함수로 보낼 때에는 "이거 정답 맞아?"라고 보내는 것이고 돌려 받을 때에는 "정답이 아니야" || "정답이야" || "정답이긴 한데, 더 좋은 답안이 있으니까 다시 보내봐" 정도의 논리가 성립된다. 때문에, Count함수에서의 조건문은 비교적 간단해도 괜찮다는 결론이 나온다.(다른 문제를 많이 풀어봐야겠다.)
