백준 BOJ 14746번 : Closest Pair
문제 난이도 : Gold V
알고리즘 분류 : 두 포인터
y = c1 위의 N개의 점과 y = c2 위의 M개의 점의 x 좌표가 주어지고 두 직선에서 점을 하나씩 고를 때 유클리드 거리가 가장 가까운 두 점의 거리를 구하고 그러한 쌍의 개수를 구하는 문제이다.
먼저 두 점 set들을 정렬해주고 투 포인터 알고리즘으로 최소 거리를 구해줄 수 있다.
최소 거리를 구한 이후에는 다시 투 포인터 알고리즘으로 최소 거리와 동일한 쌍들을 모두 count 해줄 수 있다.
탐색 자체는 투 포인터 알고리즘으로 O(N)에 되지만 어쨌든 초기에 정렬을 해줘야 하므로 최종 시간복잡도는 O(N log N)이다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N, M; cin >> N >> M;
int c1, c2; cin >> c1 >> c2;
vector<int> v(N), u(M);
for(int i=0; i<N; i++) cin >> v[i];
for(int i=0; i<M; i++) cin >> u[i];
sort(v.begin(), v.end());
sort(u.begin(), u.end());
int i = 0, j = 0, Min = INT_MAX;
while(i < N && j < M) {
Min = min(Min, abs(v[i] - u[j]));
if(v[i] < u[j]) i++;
else j++;
}
i = 0, j = 0;
int cnt = 0;
while(i < N && j < M) {
if(abs(v[i] - u[j]) == Min) cnt++;
if(v[i] < u[j]) i++;
else j++;
}
cout << Min + abs(c1 - c2) << " " << cnt << "\n";
}
백준 BOJ 2343번 : 기타 레슨
문제 난이도 : Silver I
알고리즘 분류 : 이분 탐색
구간을 구간 합이 최대 x가 되도록 M개 이하로 묶는 최소 x를 구하는 문제이다.
x를 이분 탐색으로 찾아주도록 구현할 수 있다.
구간 sum을 구하면서 cnt를 늘려주는 방식을 사용했는데, 저렇게 구현할 경우 원소 하나의 값이 임시의 x보다 클 경우에도 불구하고 cnt만 하나 늘려주고 무시하고 카운트를 진행해버린다.
따라서 저러한 경우를 없도록 하기 위해 탐색 범위의 왼쪽 끝 값을 단일 원소 중 최댓값으로 설정하였다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N, M; cin >> N >> M;
vector<int> v(N);
int Max = 0;
for(int i=0; i<N; i++) {
cin >> v[i];
Max = max(Max, v[i]);
}
int l = Max, r = 1e9, ans = 1e9;
while(l <= r) {
int m = (l + r)/2;
int cnt = 1, sum = 0;
for(int i=0; i<N; i++) {
if(sum + v[i] > m) {
cnt++;
sum = 0;
}
sum += v[i];
}
if(cnt <= M) {
ans = min(ans, m);
r = m - 1;
}
else l = m + 1;
}
cout << ans << "\n";
}
백준 BOJ 17541번 : Maratona Brasileira de Popcorn
문제 난이도 : Silver I
알고리즘 분류 : 이분 탐색
N개의 팝콘이 있고 그 양은 수열 a_i로 주어진다고 하며, M명의 인원이 릴레이로 팝콘을 먹는다고 한다.
팝콘은 반드시 주어진 순서대로 먹어야 하고 한 팝콘은 반드시 한 명이 다 먹어야 한다고 할 때, 한 명당 먹는 속도가 K라면 팝콘을 다 먹는데 얼마의 시간이 걸리는지 물어보는 문제이다.
문제를 바꿔서 생각하면 팝콘 N개를 M개의 구간으로 그 구간 합들이 최대한 균등하게 나눴을 때 몇 초가 걸리는지를 알면 된다.
K 값은 일단 무시하고 균등하게 나누기 위해 이분 탐색을 활용하자.
예를 들어 5, 8, 3, 10, 7이고 M = 3이면 (5, 8), (3, 10), (7) 정도로 나누면 될 것이다.
물론 이 때의 구간 합의 이분 탐색 값은 13이 나올 것이다.
이제 K를 이용해 시간을 구해보자.
K = 4라면, 13을 4로 나누면 나머지가 있으므로 13/4 + 1 = 4초의 시간이 걸린다.
즉, 이분 탐색 값이 x라면 (x - 1)/K + 1로 답을 구해주어야 한다.
이 문제에서 나올 수 있는 반례는 위의 문제의 반례와 동일하다.
이분 탐색의 왼쪽 끝 값이 단일 원소보다 작은 경우에도 탐색을 하면 반례가 발생하기 때문에, 원소 중에서 가장 큰 값을 왼쪽 끝 값으로 잡아야 한다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N, M, K; cin >> N >> M >> K;
vector<int> v(N);
int Max = 0;
for(int i=0; i<N; i++) {
cin >> v[i];
Max = max(Max, v[i]);
}
int l = Max, r = INT_MAX, ans = INT_MAX;
while(l <= r) {
int m = (l + r)/2;
int cnt = 1, sum = 0;
for(int i=0; i<N; i++) {
if(sum + v[i] > m) {
sum = 0;
cnt++;
}
sum += v[i];
}
if(cnt <= M) {
ans = min(ans, m);
r = m - 1;
}
else l = m + 1;
}
ans = (ans - 1)/K + 1;
cout << ans << "\n";
}
백준 BOJ 14627번 : 파닭파닭
문제 난이도 : Silver II
알고리즘 분류 : 이분 탐색
N개의 파의 길이가 주어지고 이들을 최대한 길게 같은 길이의 M개 이상의 조각들로 자른 뒤, M개 조각을 제외한 나머지 길이의 합을 구하는 문제이다.
최대 조각의 길이는 이분 탐색으로 구할 수 있다.
다만 이 문제의 핵심은 남은 길이들의 합을 구할 때, 나머지 연산으로 답을 구할 경우 실제 답보다 값이 작게 나올 수 있다는 것이다.
따라서 길이의 합을 구하고 M개 조각들의 합을 직접 빼주거나 아래처럼 모자란 길이를 추가해서 답으로 얻어주어야 AC를 받을 수 있다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N, M; cin >> N >> M;
vector<int> v(N);
for(int i=0; i<N; i++) cin >> v[i];
int l = 1, r = INT_MAX, unit = 0;
while(l <= r) {
int m = (l + r)/2;
int cnt = 0;
for(int i=0; i<N; i++) cnt += v[i] / m;
if(cnt >= M) {
unit = max(unit, m);
l = m + 1;
}
else r = m - 1;
}
int ans = 0, cnt = 0;
for(int i=0; i<N; i++) {
ans += v[i] % unit;
cnt += v[i] / unit;
}
ans += (cnt - M) * unit;
cout << ans << "\n";
}
백준 BOJ 20495번 : 수열과 헌팅
문제 난이도 : Silver I
알고리즘 분류 : 이분 탐색
N개의 수와 그 ± 오차 범위가 주어졌을 때 정렬 이후 N번째 수의 인덱스로 가능한 최소 인덱스와 최대 인덱스를 구하는 문제이다.
정렬을 해버리면 수의 순서가 섞여버리므로, 기존 수열의 순서를 보존하기 위해 벡터를 2개 + 정렬할 벡터 2개로 나누어 선언하자.
그 다음 정렬할 벡터를 정렬해주고, 최소 인덱스는 해당 원소의 최솟값과 나머지 원소들의 최댓값들로 비교하여 찾아주고, 최대 인덱스는 해당 원소의 최댓값과 나머지 원소들의 최솟값으로 비교하여 찾아주면 된다.
이 때 이분 탐색 함수인 upper_bound와 lower_bound를 활용하여 찾아주면 된다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N; cin >> N;
vector<int> v(N), u(N), vs(N), us(N);
for(int i=0; i<N; i++) {
int a, b; cin >> a >> b;
v[i] = vs[i] = a - b;
u[i] = us[i] = a + b;
}
sort(vs.begin(), vs.end());
sort(us.begin(), us.end());
for(int i=0; i<N; i++) {
cout << lower_bound(us.begin(), us.end(), v[i]) + 1 - us.begin() << " ";
cout << upper_bound(vs.begin(), vs.end(), u[i]) - vs.begin() << "\n";
}
}
백준 BOJ 16564번 : 히오스 프로게이머
문제 난이도 : Silver I
알고리즘 분류 : 이분 탐색
N개의 캐릭터의 레벨이 있고 M을 분배하여 적당히 레벨들 나누어 올린다고 할 때, N개 캐릭터 중 최소 레벨인 것의 레벨의 최댓값으로 가능한 것을 구하는 문제이다.
최소 레벨의 최댓값을 가정하고 이분 탐색을 하여 답을 얻어주면 된다.
탐색 범위의 오른쪽 끝 값은 답으로 될 수 있는 가장 큰 범위인 1e9로 설정하면 된다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N, M; cin >> N >> M;
vector<int> v(N);
for(int i=0; i<N; i++) cin >> v[i];
int l = 1, r = 1e9, ans = 1;
while(l <= r) {
int m = (l + r)/2;
int sum = 0;
for(int i=0; i<N; i++)
if(v[i] < m) sum += m - v[i];
if(sum <= M) {
ans = max(ans, m);
l = m + 1;
}
else r = m - 1;
}
cout << ans << "\n";
}
백준 BOJ 17245번 : 서버실
문제 난이도 : Silver II
알고리즘 분류 : 이분 탐색
N × N 크기의 사무실의 각 칸에 컴퓨터가 특정 높이로 쌓여있고, 1분마다 아래서부터 1층씩 냉방이 된다고 할 때 절반 이상의 컴퓨터가 냉방이 되는 최소 시간을 구하는 문제이다.
최소 시간을 먼저 가정하는 방식의 이분 탐색으로 풀이할 수 있다.
N이 최대 1,000이기 때문에 O(N^2 log (1e7))이면 충분하다.
여담으로 문제에서 주어지는 최대 높이가 1,000만 이하이기 때문에 1,000만칸짜리 벡터 2개로 누적 합을 만들어 풀어도 풀릴 것 같다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N; cin >> N;
vector<int> v(N*N);
int tot = 0;
for(int i=0; i<N*N; i++) {
cin >> v[i];
tot += v[i];
}
int l = 0, r = 1e7, ans = 1e7;
while(l <= r) {
int m = (l + r)/2;
int sum = 0;
for(int i=0; i<N*N; i++) sum += min(v[i], m);
if(sum*2 >= tot) {
ans = min(ans, m);
r = m - 1;
}
else l = m + 1;
}
cout << ans << "\n";
}
백준 BOJ 21662번 : Дипломы
문제 난이도 : Silver II
알고리즘 분류 : 이분 탐색
직사각형의 크기 w, h가 주어질 때 이 직사각형 N개를 겹치지 않고 모두 넣기 위한 최소 정사각형 한 변의 길이를 구하는 문제이다.
간단한 이분 탐색 문제이지만, w, h, n 모두 1e9 이하로 들어오므로 변의 길이는 최대 1e9 × (1e9)^(1/2)가 될 수 있다.
그런데 이 값은 제곱을 하면 long long의 범위를 넘어선다.
이러한 경우 다음의 두 가지 해결책이 있다.
1. __int128 자료형을 사용한다. 다만 이 경우 출력할 때 다시 long long 이하의 자료형으로 바꿔서 출력해야 출력이 가능하다.
2. long double 자료형을 사용한다. 다만 이 경우 오차가 발생할 수 있으므로 주의해야한다.
위의 두 가지 방법 중 편한대로 풀이하면 된다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N, M, K; cin >> N >> M >> K;
__int128 l = 1, r = 1e14, ans = 1e14;
while(l <= r) {
__int128 m = (l + r)/2;
if((m / N) * (m / M) >= K) {
ans = min(ans, m);
r = m - 1;
}
else l = m + 1;
}
int rans = ans;
cout << rans << "\n";
}
백준 BOJ 18002번 : Balanced Animals
문제 난이도 : Silver II
알고리즘 분류 : 이분 탐색
N마리의 동물들의 질량이 주어질 때, 두 그룹으로 나누어 질량을 같게 만드는 기준의 최솟값을 찾는 문제이다.
예를 들어 기준이 3이면 질량이 3보다 작은 동물들을 한 그룹, 3보다 큰 동물들을 한 그룹으로 묶어 질량의 합을 비교하는 것이다.
질량이 기준치와 같은 동물은 고려할 필요 없는 것이, 그 마릿수가 짝수일 경우 동일하게 나누고 홀수일 경우 남는 한 마리를 버린다고 하였으므로 어차피 합의 비교에는 영향이 없다.
아무튼 풀이 방식은 기준치 m을 이분 탐색으로 찾는 것이다.
문제에서 주어진 가능한 가장 큰 기준값인 2e5을 오른쪽 경곗값으로 두고 이분 탐색을 해주면 된다.
문제 조건에서 조건을 만족하는 m이 반드시 존재한다고 하였으므로 예외 처리는 해줄 필요가 없다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N; cin >> N;
vector<int> v(N);
for(int i=0; i<N; i++) cin >> v[i];
sort(v.begin(), v.end());
int l = 1, r = 2e5, ans = 2e5;
while(l <= r) {
int m = (l + r)/2;
int a = 0, b = 0;
for(int i=0; i<N; i++) {
if(v[i] < m) a += v[i];
else if(v[i] > m) b += v[i];
}
if(a >= b) {
ans = min(ans, m);
r = m - 1;
}
else l = m + 1;
}
cout << ans << "\n";
}
참고로 이 문제는 백준 BOJ 21887번 : 'Pulling Their Weight'와 완전히 동일한 문제이다.
백준 BOJ 2428번 : 표절
문제 난이도 : Silver III
알고리즘 분류 : 이분 탐색
길이 N인 수열에 대해 두 수 a_i, a_j를 선택하여 a_i × 0.9 ≤ a_j ≤ a_i를 만족하는 순서쌍 (i, j)의 수를 구하는 문제이다.
bound 함수를 활용하여 문제를 해결해보자.
오름차순 정렬을 해주면, 어떤 원소보다 왼쪽에 있는 모든 원소들에 대해서 일단 a_j ≤ a_i는 만족한다.
따라서 lower_bound로 a_i × 0.9 ≤ a_j를 만족하는 i의 위치만 찾아주면 된다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N; cin >> N;
vector<int> v(N);
for(int i=0; i<N; i++) {
int x; cin >> x;
v[i] = x * 10;
}
sort(v.begin(), v.end());
int ans = 0;
for(int i=N-1; i>=0; i--) {
ans += (v.begin()+i) - lower_bound(v.begin(), v.begin()+i, v[i]/10*9);
}
cout << ans << "\n";
}
백준 BOJ 15810번 : 풍선 공장
문제 난이도 : Silver II
알고리즘 분류 : 이분 탐색
N명의 스태프가 하나의 풍선을 부는데 걸리는 시간 a_i가 각각 주어지고, M개의 풍선을 완성하는데 걸리는 최소 시간을 구하는 문제이다.
시간을 먼저 가정하고 M개 이상의 풍선을 불 수 있는지 여부를 확인하여 탐색 범위를 바꾸는 이분 탐색으로 풀이할 수 있다.
이 문제의 핵심은 스태프가 1명이고 a_1 = 1e6, M = 1e6이면 답이 최대 1e12가 될 수 있으므로 탐색 범위를 1e12까지 잡아주어야 한다는 것이다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N, M; cin >> N >> M;
vector<int> v(N);
for(int i=0; i<N; i++) cin >> v[i];
int l = 1, r = 1e12, ans = 1e12;
while(l <= r) {
int m = (l + r)/2;
int cnt = 0;
for(int i=0; i<N; i++) cnt += m / v[i];
if(cnt >= M) {
ans = min(ans, m);
r = m - 1;
}
else l = m + 1;
}
cout << ans << "\n";
}
백준 BOJ 24999번 : Prom
문제 난이도 : Silver III
알고리즘 분류 : 이분 탐색
배열 A와 B가 주어졌을 때 두 배열에서 원소를 하나씩 뽑아 그 차이값이 K 이하인 쌍의 수를 구하는 문제이다.
즉 -K ≤ b_i - a_i ≤ K를 만족하면 되고 a_i를 넘겨보면 a_i - K ≤ b_i ≤ a_i + K를 만족하는 b_i를 찾으면 되므로, 배열 B를 정렬해준 뒤 upper_bound와 lower_bound로 O(N log M) 시간에 답을 찾을 수 있다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N, M, K; cin >> N >> M >> K;
vector<int> v(N), u(M);
for(int i=0; i<N; i++) cin >> v[i];
for(int i=0; i<M; i++) cin >> u[i];
sort(v.begin(), v.end());
sort(u.begin(), u.end());
int ans = 0;
for(int i=0; i<N; i++) {
ans += upper_bound(u.begin(), u.end(), v[i]+K)
- lower_bound(u.begin(), u.end(), v[i]-K);
}
cout << ans << "\n";
}
백준 BOJ 17393번 : 다이나믹 롤러
문제 난이도 : Silver III
알고리즘 분류 : 이분 탐색
수열 A와 오름차순 정렬된 수열 B가 주어지고, a_i (1 ≤ i ≤ N)에 대해 j > i이면서 b_j ≤ a_i인 b_j의 수를 구하는 문제이다.
수열 B가 오름차순이라는 조건이 문제 중간에 살짝 언급되어서 문제를 자세히 읽지 않으면 방향을 놓칠 가능성이 높다.
i+1 ~ N 구간에 대해 a_i 이하인 원소들을 찾으면 되므로 upper_bound를 이용해주면 된다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N; cin >> N;
vector<int> v(N), u(N);
for(int i=0; i<N; i++) cin >> v[i];
for(int i=0; i<N; i++) cin >> u[i];
for(int i=0; i<N; i++) {
cout << upper_bound(u.begin()+i+1, u.end(), v[i]) - (u.begin()+i+1) << " ";
}
cout << "\n";
}
백준 BOJ 17451번 : 평행 우주
문제 난이도 : Silver III
알고리즘 분류 : 그리디
0번 행성에서 1 ~ N-1번 행성을 순서대로 돌고 N번 행성으로 돌아온다고 할 때 각 이동에 필요한 최소 속도가 주어질 때, 속도를 유지하거나 감소시켜 최소 속도의 배수로 속도를 맞춰야 한다고 하면 처음 출발 속도의 최솟값이 얼마인지 구하는 문제이다. (설명이 복잡하니 문제 원문을 읽어보는 것을 추천한다.)
아무튼 이 문제를 풀이하는 방법은 이분 탐색도 있겠지만 더 간단한 풀이는 역순으로 생각하여 속도를 점차 늘려가며 최솟값을 찾는 것이다.
만약 현재 답이 어떤 이동의 최소 속도 이하이라면 최소 속도로 값을 바꿔주고, 최소 속도보다 큰데 최소 속도의 배수가 아니라면 최소 속도의 배수이면서 현재 답보다 큰 값 중 가장 작은 것으로 갱신해주면 된다.
N = 1일 때도 최소 속도 이상으로 이동을 해야함에 유의하자. (지구에서 지구로 가는 것인데 어쨌든 발사는 해야한다.)
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N; cin >> N;
vector<int> v(N);
for(int i=0; i<N; i++) cin >> v[i];
int ans = 0;
for(int i=N-1; i>=0; i--) {
if(ans <= v[i]) ans = v[i];
else if(ans % v[i] != 0) ans = (ans / v[i] + 1) * v[i];
}
cout << ans << "\n";
}
백준 BOJ 11561번 : 징검다리
문제 난이도 : Silver III
알고리즘 분류 : 이분 탐색
N칸짜리 징검다리를 건너는데 도약 거리는 이전에 뛴 거리보다 많이 뛰어야한다고 할 때 징검다리를 최대한 많이 밟을 수 있는 개수를 구하는 문제이다.
N이 1 ~ k의 합 이상이고 1 ~ k+1의 합보다 작으면 k번 뛰는 것이 최선이다.
따라서 k * (k + 1) / 2 <= N인 최대의 k를 이분 탐색으로 구해주면 된다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int T; cin >> T;
while(T--) {
int N; cin >> N;
int l = 1, r = INT_MAX, ans = 0;
while(l <= r) {
int m = (l + r)/2;
int sum = m * (m + 1) / 2;
if(sum <= N) {
ans = max(ans, m);
l = m + 1;
}
else r = m - 1;
}
cout << ans << "\n";
}
}
백준 BOJ 24345번 : УЧИЛИЩЕН КОНЦЕРТ
문제 난이도 : Silver II
알고리즘 분류 : 이분 탐색
M개의 컴퓨터가 각각 디스크 하나를 굽는 시간이 주어질 때 N개의 디스크를 굽는 최소 시간을 구하는 문제이다.
위의 많은 문제들의 풀이와 비슷한 방식으로 시간에 대한 이분 탐색을 하여 답을 간단히 구해줄 수 있다.
이 때 N = 1e5이고 M = 1e5인 경우 답이 최대 1e10이 될 수 있으므로 오른쪽 끝 탐색 범위를 1e10 이상으로 잡아주어야 한다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N, M; cin >> N >> M;
vector<int> v(M);
for(int i=0; i<M; i++) cin >> v[i];
int l = 1, r = 1e10, ans = 1e10;
while(l <= r) {
int m = (l + r)/2;
int sum = 0;
for(int i=0; i<M; i++) sum += m / v[i];
if(sum >= N) {
ans = min(ans, m);
r = m - 1;
}
else l = m + 1;
}
cout << ans << "\n";
}
백준 BOJ 7419번 : Cable master
문제 난이도 : Silver III
알고리즘 분류 : 이분 탐색
N개 케이블의 길이가 주어지고 이들을 같은 길이들로 잘라 M개의 조각을 만들어야 한다고 할 때 조각의 길이의 최댓값을 구하는 문제이다.
주어지는 길이가 소숫점 2자리까지 주어지고 답 또한 2자리까지 구해야 하는데, 실수형 자료형을 사용할 경우 오차가 발생할 여지가 있으므로 100을 곱하여 답을 구해준 뒤 그 답을 100을 나누어 주는 방식을 사용하자.
정수형으로 바꾸면 간단한 이분 탐색 문제가 되므로, 답으로 얻을 길이를 이분 탐색으로 찾으면 된다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N, M; cin >> N >> M;
vector<int> v(N);
for(int i=0; i<N; i++) {
double x; cin >> x;
v[i] = x * 100;
}
int l = 1, r = INT_MAX, ans = 0;
while(l <= r) {
int m = (l + r)/2;
int cnt = 0;
for(int i=0; i<N; i++) cnt += v[i] / m;
if(cnt >= M) {
ans = max(ans, m);
l = m + 1;
}
else r = m - 1;
}
cout << fixed;
cout.precision(2);
cout << (double)ans/100 << "\n";
}
'알고리즘 > 알고리즘 공부 내용 정리' 카테고리의 다른 글
| 백준 BOJ 풀이 : BFS 문제들 위주 풀이 (그래프 탐색) 220725 (0) | 2022.07.25 |
|---|---|
| 백준 BOJ 풀이 : 데이크스트라, 이분 탐색, 그래프 등 220724 (0) | 2022.07.24 |
| 백준 BOJ 풀이 : 이분 탐색 문제들 위주 풀이 (220722) (0) | 2022.07.22 |
| 백준 BOJ 풀이 : 이분 탐색, 조합론(완전순열, 카탈란 수) 문제 등 (220721) (0) | 2022.07.21 |
| 220720 백준 BOJ 풀이 : LIS (가장 긴 증가하는 부분 수열) 문제들 (0) | 2022.07.20 |