삼성에서 이제 STL 못쓰게 막아놨대서... 직접 정렬을 구현했다.
정렬구현하는시간 > 문제푼시간
더보기
이분탐색은 'X에 대해 이 답이 가능해? (응/아니)' 라고 답할 수 있는 문제에 적용할 수 있는데
문제 예시에서
> 구간의 길이가 최대 251일때 다솜이가 고속도로에 새로 세울 수 있는 휴게소의 개수는 몇개일까요?
> 그럼 구간의 길이가 최대 125라면 다솜이가 고속도로에 새로 세울 수 있는 휴게소의 개수는 몇개일까요?
문제 예시에서
> 구간의 길이가 최대 251일때 다솜이가 고속도로에 새로 세울 수 있는 휴게소의 개수는 몇개일까요?
> 그럼 구간의 길이가 최대 125라면 다솜이가 고속도로에 새로 세울 수 있는 휴게소의 개수는 몇개일까요?
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
|
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int n, m, res = 1000000000;
int position[101];
int difference[101];
void merge_sort(int left, int right) {
// partition
if (left < right) {
int mid = (left + right) / 2;
merge_sort(left, mid);
merge_sort(mid + 1, right);
// merge
int temp[100];
int i = left, j = mid + 1;
int idx = 0;
while (i <= mid && j <= right) {
if (position[i] < position[j]) temp[idx++] = position[i++];
else temp[idx++] = position[j++];
}
// 남은거
while (i <= mid) {
temp[idx++] = position[i++];
}
while (j <= right) {
temp[idx++] = position[j++];
}
idx = 0;
for (int i = left; i <= right; i++) {
position[i] = temp[idx++];
}
}
}
int max(int first, int second) {
if (first > second) return first;
else return second;
}
int min(int first, int second) {
if (first > second) return second;
else return first;
}
bool solve(int mid) {
int num = 0;
for (int i = 0; i < n + 1; i++) {
num += difference[i] / mid;
if (!(difference[i] % mid)) {
num -= 1;
}
}
if (num > m) return false;
else return true;
}
int main() {
int L;
scanf("%d %d %d", &n, &m, &L);
int left = 0, right = 0;
for (int i = 0; i < n; i++) {
scanf("%d", &position[i]);
}
position[n] = L;
merge_sort(0, n);
int prev = 0;
for (int i = 0; i < n + 1; i++) {
difference[i] = position[i] - prev;
prev = position[i];
right = max(right, difference[i]);
}
while (left <= right) {
int mid = (left + right) / 2;
if (solve(mid)) {
res = min(res, mid);
right = mid - 1;
}
else {
left = mid + 1;
}
}
printf("%d\n", res);
}
|
cs |
