https://www.acmicpc.net/problem/3079
문제
> 상근이와 친구들은 오스트레일리아로 여행을 떠났다.
> 상근이와 친구들은 총 M명이고, 지금 공항에서 한 줄로 서서 입국심사를 기다리고 있다. 입국심사대는 총 N개가 있다.
> 각 입국심사관이 심사를 하는데 걸리는 시간은 사람마다 모두 다르다.
> k번 심사대에 앉아있는 심사관이 한 명을 심사를 하는데 드는 시간은 Tk이다.
> 가장 처음에 모든 심사대는 비어있고, 심사를 할 준비를 모두 끝냈다.
> 상근이와 친구들은 비행기 하나를 전세내고 놀러갔기 때문에, 지금 심사를 기다리고 있는 사람은 모두 상근이와 친구들이다.
> 한 심사대에서는 한 번에 한 사람만 심사를 할 수 있다.
> 가장 앞에 서 있는 사람은 비어있는 심사대가 보이면 거기로 가서 심사를 받을 수 있다. 하지만 항상 이동을 해야 하는 것은 아니다.
> 더 빠른 심사대의 심사가 끝나길 기다린 다음에 그 곳으로 가서 심사를 받아도 된다.
> 상근이와 친구들은 모두 컴퓨터 공학과 학생이기 때문에, 어떻게 심사를 받으면 모든 사람이 심사를 받는데 걸리는 시간이 최소가 될지 궁금해졌다.
> 예를 들어, 두 심사대가 있고, 심사를 하는데 걸리는 시간이 각각 7초와 10초라고 하자.
> 줄에 서 있는 사람이 6명이라면, 가장 첫 두 사람은 즉시 심사를 받으러 가게 된다.
> 7초가 되었을 때, 첫 번째 심사대는 비어있게 되고,
세 번째 사람이 그곳으로 이동해서 심사를 받으면 된다.
> 10초가 되는 순간, 네 번째 사람이 이곳으로 이동해서 심사를 받으면 되고,
14초가 되었을 때는 다섯 번째 사람이 첫 번째 심사대로 이동해서 심사를 받으면 된다.
> 20초가 되었을 때, 두 번째 심사대가 비어있게 된다. 하지만, 여섯 번째 사람이 그 곳으로 이동하지 않고, 1초를 더 기다린 다음에 첫 번째 심사대로 이동해서 심사를 받으면, 모든 사람이 심사를 받는데 걸리는 시간이 28초가 된다.
> 만약, 마지막 사람이 1초를 더 기다리지않고, 첫 번째 심사대로 이동하지 않았다면, 모든 사람이 심사를 받는데 걸리는 시간이 30초가 되게 된다.
> 상근이와 친구들이 심사를 받는데 걸리는 시간의 최솟값을 구하는 프로그램을 작성하시오.접근
이분 탐색으로 걸리는 시간을 기준으로 잡아 해당 시간동안 M명의 인원수를 전부 심사할 수 있는지, 없는지로 다음의 탐색범위를 설정해 재귀해준다.
예를 들어 60초 안에는 10초, 7초 심사대로 하면 M이 6명일 때, 6명 + 8명 총 14명까지 된다.
즉, 좀 더 시간을 줄여도 괜찮으니 60초를 이분탐색으로 반 줄여 30초에서 따진다.
30초에선 3+4로 7명까지 되니 좀 더 줄인다. 15초면 1+2 3명이라 다 심사를 못하므로 시간을 좀 늘린다. 이런식으로 걸리는 시간을 기준으로 탐색한다.
문제해결
> 문제에 주어진 변수들의 범위에 맞게 long long 형으로 선언을 해주고 심사대 수, 심사할 인원수, 심사대 별 걸리는 시간(test 벡터)를 입력받는다.
> 최악의 경우 젤 오래걸리는 심사대 10억 x 최대 M명 10억 이므로 너무 커진다.
따라서 심사대별 시간을 입력받으면서 가장 오래걸리는 심사대의 시간을 찾아놓는다. 이 시간과 입력받은 M을 곱해 최악의 시간(right값)을 구한다.
> 1초부터 위에서구한 right로 Test메소드를 통해 이분탐색을 한다. 탈출 방법과, 중앙값을 구하는걸 선언해준다.
> sum을 통해 mid(주어진 시간)동안 각 심사대에서 볼 수 있는 인원수를 구해 다 더한다.
> 이 sum이 M을 넘어가면 시간이 충분하므로 더 보지않고 break하며 범위를 left, mid-1로 더 줄여 재귀한다.
> 그렇지 않으면 M보다 작으므로 범위를 늘리기 위해 mid+1,right로 범위를 늘려 탐삭한다.
> 최종적으로 left>right에 걸려 rst(현재까지의 최소의 걸리는 시간)가 반환된다. 이를 출력한다.코드
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
long long N, M;
vector<long long> test;
long long Test(long long left, long long right, long long rst)
{
if (left > right) return rst;
long long mid = (left + right) / 2;
long long sum = 0;
for (int i = 0; i < N; i++)
{
sum += (mid / test[i]);
if (sum >= M) break;
}
if (sum >= M) return Test(left, mid - 1, mid);
else return Test(mid + 1, right, rst);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> N >> M;
test.resize(N);
long long Max = 0;
for (int i = 0; i < N; i++)
{
cin >> test[i];
Max = max(Max, test[i]);
}
long long end = Max * M;
cout << Test(1, end, end) << '\n';
}
후기
로직은 제대로 짜서 결과는 맞게 나왔는데 백준에선 틀렸다. 이는 범위에 문제가 있거나, 오버플로우 등이 일어난다는거다.
처음엔 Test메소드에 end가 아닌 10억으로 잘못된 값을 넣었고 다음엔 10억 x M값을 넣었다. 이것도 크기 때문에 최종적으로 test벡터의 최대값에 M을 구하는 방식으로 헀다. 가장 효율적이다.
그리고 이분탐색 재귀에서 sum누적 부분에서 끝까지 돌고 sum이 M보다 어떤지 판단했는데 최악의 경우엔 여기서 오버플로우가 발생한다고 한다. 그래서 sum이 M보다 크면 더 볼 필요가 없으므로 깨고 나와 다음 재귀를 해준다.
이렇게 두개를 처리해주니 정답이 됐다.
