44. 마구간 정하기
인프런의 it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비 강의를 수강하여 공부한 내용을 기록한 포스트입니다. 문제는 공개하지 않습니다.
풀이과정
43번 문제와 마찬가지로 이분검색 문제이다. 이분검색 문제에서는 이분검색할 범위를 찾는 것이 중요한 것 같다.
- 이분검색할 최대 범위를 찾는다. 이 범위는 배열의 크기가 아니므로 프로그래머가 찾아야한다.
- 그 값이 조건에 타당한지 검사 후 계속 이분검색을 수행하여 답을 찾는다.
이 문제는 이분검색할 범위를 입력의 최대값으로 정해야 해서 먼저sort()를 통해 오름차순으로 정렬해주었다.1~(입력의최댓값)이라는 범위를 찾고 나니 값을 결정하는 것은 쉬웠다.
코드
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n, m;
scanf("%d %d", &n, &m);
vector<int> arr(n);
for (int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
sort(arr.begin(), arr.end());
int left = 1, right = arr[n - 1] - arr[0], mid;
int cnt, res = 0, pre = 0;
while (left <= right) {
mid = (left + right) / 2;
cnt = 1;
pre = 0;
for (int i = 1; i < n; i++) {
if (arr[i] - arr[pre] >= mid) {
cnt++;
pre = i;
}
}
if (cnt >= m) {
res = mid;
left = mid + 1;
}
else {
right = mid - 1;
}
}
printf("%d", res);
return 0;
}
REFERENCE