중요한 이분탐색 문제.
서로다른 길이를 a로 나눠서 n개 이상의 랜선을 만들어야 한다.
a로 나눠야 하는 최소 길이는 1이다.
최대 길이는 주어진 랜선 중에 가장 긴 랜선이다.
1부터 최대 길이까지 나눠보는데, 이분 탐색을 이용한다.
기본은 (low + high ) / 2 = mid 임을 이용한다.
mid 길이로 모든 랜선을 나눠서 몇 개 count 의 랜선이 나오는지 센다.
만약 결과count가 목표개수 n 보다 적게 나온다면, 더 짧은 길이로 나눠야 더 많은 개수가 나올 것이다.
따라서 count < n 이라면, 최대 길이 end = mid -1 로 줄인다.
count가 n개와 같거나 크다면, start = mid +1 로 늘려서 더 길게 나눠도 n개 이상임을 만족하는지 탐색한다.
#include <bits/stdc++.h>
using namespace std;
int k, n; // 가지고있는 랜선 개수, 필요한 개수
int maxlen;
int line[10002];
long long mid, high, low;
int count(int t){
int cnt = 0 ;
for(int i = 0; i < k; i++) cnt += (line[i] / t);
return cnt;
}
int main(void){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> k >> n;
for(int i = 0; i < k; i++){
cin >> line[i];
if(maxlen < line[i]) maxlen = line[i];
}
high = maxlen, low = 1; //최대길이, 최소길이
long long answer = 0;
while(low <= high){ /* 이분탐색 */
mid = (low + high)/ 2;
int cnt = count(mid); // 개수 세기
if(cnt >= n) {
low = mid + 1;
if(answer < mid) answer = mid;
}
else {
high = mid - 1;
}
}
cout << answer;
return 0;
}
#include <bits/stdc++.h>
using namespace std;
int k, n;
long long answer, maxlen;
long long v[10002];
int count(int temp){
int cnt = 0;
for(int i = 0; i < k; i++) cnt += (v[i] / temp);
return cnt;
}
void binary(long long start, long long end){
if(start > end) return;
long long mid = (start + end)/2;
long long cnt = count(mid); 개수 세기
if(cnt >= n){
answer = max(answer, mid);
binary(mid + 1, end);
}
else{
binary(start, mid - 1);
}
}
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> k >> n;
for(int i = 0; i < k; i++){
cin >> v[i];
maxlen = max(maxlen, v[i]);
}
binary(1, maxlen);
cout << answer;
return 0;
}
728x90
'알고리즘 > 백준' 카테고리의 다른 글
| 방 번호 백준 1475번 c++ (0) | 2022.02.14 |
|---|---|
| 영화감독 숌 백준 1436번 c++ (0) | 2022.02.14 |
| 카드 백준 11652번 c++ (0) | 2022.02.13 |
| 쇠막대기 백준 10799번 c++ (0) | 2022.02.13 |
| 괄호 백준 9012번 c++ (0) | 2022.02.13 |