https://www.acmicpc.net/problem/16401
16401번: 과자 나눠주기
첫째 줄에 조카의 수 M (1 ≤ M ≤ 1,000,000), 과자의 수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 과자 N개의 길이 L1, L2, ..., LN이 공백으로 구분되어 주어진다. 과자의 길이는 (1 ≤ L1, L2, ..., LN ≤ 1,000,000,000) 를 만족한다.
www.acmicpc.net
이분 탐색으로 조카들에게 나눠줄 수 있는 과자의 최대 길이를 찾아줘야 한다.
이분 탐색의 처음 범위는 1개를 나눠줄 수 있는 경우부터 가지고 있는 과자 중 가장 큰 과자의 길이까지가 된다.
3 10
1 2 3 4 5 6 7 8 9 10
문제의 첫 번째 예시처럼 다음과 위와 같이 막대과자를 가지고 있다면 1에서 10까지의 범위를 탐색해준다.
4 3
10 10 15
2번째 예제에서의 범위는 1부터 15까지이다.
문제의 예시에서는 막대과자의 길이가 모두 정렬된 순서로 되어있지만 히든 케이스에서는 정렬되어 있지 않을 수도 있으므로 입력받은 막대과자의 길이 배열을 정렬해놓고 탐색을 시작한다.
이분 탐색으로 매번 mid값을 구해서 mid길이만큼을 조카들에게 나눠줄 수 있는지 검사한다.
나눠줄 수 있다면 더 큰 길이로 나눠줄 수 있는지 mid값보다 큰 범위를 탐색하고, 나눠줄 수 없다면 더 작은 길이를 찾아야 한다.
나눠줄 수 있는지 검사할 때에는 길이가 긴 막대과자들부터 mid길이만큼을 나눌 수 있는지 확인한다. 배열을 앞에서 정렬해놓았으므로 배열의 뒤쪽부터 검사해주면 된다. mid길이만큼의 막대과자가 조카의 수이상 나온다면 mid 길이만큼씩 나누어줄 수 있다.
|
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
|
#include <iostream>
#include <algorithm>
using namespace std;
int M, N;
int ans;
int arr[1000001];
bool check(int len) {
int tmp;
int cnt = 0;
//배열의 맨 뒤(큰 값)부터 검사
for (int i = N - 1; i >= 0; i--) {
if (arr[i] < len) break;
tmp = arr[i];
while (tmp >= len) {
cnt++;
tmp -= len;
}
//len만큼의 길이가 조카의 수만큼 나온다면 바로 true를 리턴
if (cnt >= M) return true;
}
if (cnt >= M) return true;
else return false;
}
void binarySearch(int left, int right) {
if (left > right) return;
int mid = (left + right) / 2;
//막대 과자 길이가 mid일때, 조카들에게 나눠줄 수 있는지 검사
bool res = check(mid);
if (res) {
//나눠줄 수 있다면 일단 길이를 저장해놓고, 더 큰 길이를 나눠줄 수 있는지 탐색
if (ans < mid) ans = mid;
binarySearch(mid + 1, right);
}
else {
//mid 길이 만큼씩 나눠줄 수 없다면 더 작은 길이를 나눠줘야한다.
binarySearch(left, mid - 1);
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> M >> N;
for (int i = 0; i < N; i++) cin >> arr[i];
sort(arr, arr + N);
ans = 0;
binarySearch(1, arr[N - 1]);
cout << ans << '\n';
return 0;
}
Colored by Color Scripter
|
'BOJ' 카테고리의 다른 글
| [BOJ] 17090. 미로 탈출하기 (0) | 2020.05.01 |
|---|---|
| [BOJ] 2174. 로봇 시뮬레이션 (0) | 2020.04.28 |
| [BOJ] 10711. 모래성 (0) | 2020.04.27 |
| [BOJ] 2866. 문자열 잘라내기 (0) | 2020.04.21 |
| [BOJ] 5427. 불 (0) | 2020.04.19 |