문제
https://www.acmicpc.net/problem/3079
풀이
- 사용 알고리즘 : 파라메트릭 서치
- 시간 복잡도 : $O(N * log(M * min(T_{k})))$
파라메트릭 서치로 풀 수 있는 문제였습니다.
이 문제에서의 큰 문제점은 $M$의 상한이 $10^{9}$이라는 점입니다. 완전 탐색 시 발생하는 시간은 대략 $O(N^{M})$ 정도일 테고, 당연히 터집니다. $M$의 상한이 너무 크니, 이를 로그 시간으로 최적화시킬 필요가 있습니다.
생각해 볼 수 있는 접근은, 심사를 받는 데 걸리는 시간의 최솟값이 얼마인가? 라는 최적화 관점에서, 임의의 심사 시간 $x$에 대하여 $M$명의 사람들을 모두 심사하는 데 $x$ 시간 안에 가능한가? 라는 결정 문제 관점으로 바꾸어 생각해 보는 겁니다.
만약 $x$ 시간안에 가능했다면, $x$보다 더 최소의 시간을 찾아 심사가 가능한지 아닌지 여부를 반복해서 확인해 주면 되겠죠.
이때 임의의 심사 시간 $x$는 이분 탐색을 이용하여 정할 수 있습니다.
가능한 심사 시간의 하한 $low$와 상한 $high$ 범위를 설정해주고, 범위 사이의 수 $x$를 임의대로 지정해 줍니다. 그리고 심사 시간 $x$에 대해 $M$명의 사람들이 모두 심사 가능한지 판단해 주는데, 만약 심사가 가능했다면 기존의 심사 시간 $x$ 값을 더 낮춰서 시도해볼만하겠죠. 따라서 이 경우에는 따져봐야 할 범위가 기존의 범위 $[low, high]$에서 범위 $[low, x - 1]$ 로 줄어들게 됩니다.
만약 심사가 불가능했다면 기존의 심사 시간 $x$ 값을 더 높여서 다시 시도해야 합니다. 따라서 이 경우에는 따져봐야 할 범위가 기존의 범위 $[low, high]$에서 범위 $[x + 1, high]$ 로 줄어들게 됩니다.
이러한 흐름은 이분 탐색의 로직과 똑같습니다. $M$명의 사람들 모두 심사 가능한 최소의 $x$ 시간을 이분 탐색으로 찾아주는 거죠.
그렇다면 심사 시간 $x$에 대해 $M$명의 사람들이 모두 심사 가능한지 판단은 어떻게 할 수 있을까요?
최대한 그리디 하게 생각해 주면 되는데, $x$ 시간 동안 각 심사대를 한 번도 비우지 않고 최대로 사람을 심사했을 때 총 몇 명을 심사할 수 있는지 세주기만 하면 됩니다.
이는 총 심사 시간 $x$를 심사대에서 심사하는 데 걸리는 시간 $T_{k}$로 나눴을 때의 몫을 취해 더해주면 되겠죠.
예를 들어, 총 심사 시간이 30이라 했을 때 심사대 A에서 걸리는 시간이 7이라면, 심사대 A에서 최대로 심사할 수 있는 사람의 수는 4명이 되는 식입니다.
이런 식으로 총 심사 시간 $x$에 대해서 $T_{k}$로 나눈 모든 몫을 다 더해준 값이 $sum$이라고 했을 때, $sum \geq M$ 이라면 $x$ 시간 안에 $M$명 모두 심사 가능하다는 뜻이 되고, $sum < M$ 이라면 $x$ 시간 안에 $M$명을 심사할 수 없다는 뜻이 됩니다.
이제 아이디어는 다 정리해 봤으니, 시간 복잡도 분석을 해봅시다.
먼저 가능한 심사 시간의 범위부터 대략적으로 따져보면, 하한은 1이 될 거고 상한은 $M * min(T_{k})$가 될 겁니다. 그렇다면 저 범위 안에서 최소의 시간을 찾는 데 걸리는 시간은 이분 탐색을 사용하니 $O(log(M * min(T_{k})))$ 정도가 되겠죠.
또한, 심사 시간 $x$에 대해 $M$명의 사람들이 모두 심사 가능한지 판단하는 시간은 입국 심사대의 수만큼 들 테니 $O(N)$이 될 것이니, 이 문제는 $O(N * log(M * min(T_{k})))$ 시간 안에 해결할 수 있습니다.
마지막으로 주의해야 할 점은, $T_{k}$의 상한이 상당히 커서 중간 연산 과정에서 오버플로우가 발생할 확률이 있습니다. 이 부분만 주의해서 코드 작성하시면 맞왜틀은 피하실 수 있을 겁니다..(경험담)
코드
#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const ll INF = 1e18;
const int inf = 2e9;
const int SIZE = 1 << 18;
const int MOD = 1e9 + 7;
int main(void){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, m;
cin >> n >> m;
vector<int> v;
int minn = inf;
for (int i = 0; i < n; i++) {
int k;
cin >> k;
v.push_back(k);
minn = min(minn, k);
}
ll lo = 1;
ll hi = (ll) minn * m;
ll mid;
int vSize = v.size();
ll ans = INF;
while (lo <= hi) {
mid = (lo + hi) >> 1; // 심사하는데 걸린 총 시간
ll cnt = 0; // 심사받을 수 있는 최대 인원 수
for (int i = 0; i < vSize; i++) {
cnt += mid / v[i];
}
if (cnt >= m) {
ans = min(ans, mid);
hi = mid - 1;
}
else {
lo = mid + 1;
}
}
cout << ans;
return 0;
}
'Problem Solving > 백준' 카테고리의 다른 글
백준 20444번 | 색종이와 가위 (C++ 풀이) (2) | 2023.05.28 |
---|---|
백준 1719번 | 택배 (C++ 풀이) (0) | 2023.05.14 |
백준 16724번 | 피리 부는 사나이 (C++ 풀이) (1) | 2023.01.25 |
백준 16946번 | 벽 부수고 이동하기 4 (C++ 풀이) (1) | 2022.10.25 |
백준 13511번 | 트리와 쿼리 2 (C++ 풀이) (0) | 2022.10.02 |
댓글