문제
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
코드
최종 풀이
#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
int n, m, i, lt, rt, mid, pos, cnt, res;
scanf("%d %d", &n, &m);
vector<int> a(n);
for(i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
sort(a.begin(), a.end());
lt = a[1];
rt = a[n];
while(lt <= rt) {
cnt = 1;
mid = (lt + rt) / 2; // 5
pos = a[1];
for(i = 2; i <= n; i++) {
if(a[i] - pos >= mid) {
cnt++;
pos = a[i];
}
}
if(cnt >= m) {
res = mid;
lt = mid + 1;
} else {
rt = mid - 1;
}
}
printf("%d", res);
return 0;
}
설명
사용자로부터 N과 M을 입력받는다. 마구간의 좌표를 N번 만큼 입력받아 vector a에 할당하고 퀵정렬을 통해 오름차순으로 정렬한다.
이분탐색을 활용하여 가까운 두 말의 거리가 최대값을 구한다.
lt와 rt 각각 첫 번째와 마지막좌표를 할당하고 while문을 돌려 mid값을 할당해나간다.
두말의 거리가 mid보다 작거나 같을 경우 배치가 가능하므로 cnt를 1씩 증가하고 해당 좌표를 pos에 할당해나가면서 각 배치가 가능한 경우를 counting한다.
해당 mid에 대한 counting끝난 후 cnt값이 m보다 크거나 같을 경우 최대값에 속하므로 mid를 res에 할당하고 이전의 값들은 속하지 않으므로 lt를 mid + 1로 할당한다. 작을 경우 이후의 값들에 속하지 않으므로 rt를 mid - 1로 할당한다.
마지막으로 거리의 최대값에 해당하나는 res출력하여 마무리한다.
해당 내용은 김태원님의 'it 취업을 위한 알고리즘 문제풀이' 강의를 듣고 작성한 글입니다.
