문제
상근이와 친구들은 오스트레일리아로 여행을 떠났다. 상근이와 친구들은 총 M명이고, 지금 공항에서 한 줄로 서서 입국심사를 기다리고 있다. 입국심사대는 총 N개가 있다. 각 입국심사관이 심사를 하는데 걸리는 시간은 사람마다 모두 다르다. k번 심사대에 앉아있는 심사관이 한 명을 심사를 하는데 드는 시간은 Tk이다.
가장 처음에 모든 심사대는 비어있고, 심사를 할 준비를 모두 끝냈다. 상근이와 친구들은 비행기 하나를 전세내고 놀러갔기 때문에, 지금 심사를 기다리고 있는 사람은 모두 상근이와 친구들이다. 한 심사대에서는 한 번에 한 사람만 심사를 할 수 있다. 가장 앞에 서 있는 사람은 비어있는 심사대가 보이면 거기로 가서 심사를 받을 수 있다. 하지만 항상 이동을 해야 하는 것은 아니다. 더 빠른 심사대의 심사가 끝나길 기다린 다음에 그 곳으로 가서 심사를 받아도 된다.
상근이와 친구들은 모두 컴퓨터 공학과 학생이기 때문에, 어떻게 심사를 받으면 모든 사람이 심사를 받는데 걸리는 시간이 최소가 될지 궁금해졌다.
예를 들어, 두 심사대가 있고, 심사를 하는데 걸리는 시간이 각각 7초와 10초라고 하자. 줄에 서 있는 사람이 6명이라면, 가장 첫 두 사람은 즉시 심사를 받으러 가게 된다. 7초가 되었을 때, 첫 번째 심사대는 비어있게 되고, 세 번째 사람이 그곳으로 이동해서 심사를 받으면 된다. 10초가 되는 순간, 네 번째 사람이 이곳으로 이동해서 심사를 받으면 되고, 14초가 되었을 때는 다섯 번째 사람이 첫 번째 심사대로 이동해서 심사를 받으면 된다. 20초가 되었을 때, 두 번째 심사대가 비어있게 된다. 하지만, 여섯 번째 사람이 그 곳으로 이동하지 않고, 1초를 더 기다린 다음에 첫 번째 심사대로 이동해서 심사를 받으면, 모든 사람이 심사를 받는데 걸리는 시간이 28초가 된다. 만약, 마지막 사람이 1초를 더 기다리지않고, 첫 번째 심사대로 이동하지 않았다면, 모든 사람이 심사를 받는데 걸리는 시간이 30초가 되게 된다.
상근이와 친구들이 심사를 받는데 걸리는 시간의 최솟값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 1,000,000,000)
다음 N개 줄에는 각 심사대에서 심사를 하는데 걸리는 시간인 가 주어진다. (1 ≤ ≤ )
출력
첫째 줄에 상근이와 친구들이 심사를 마치는데 걸리는 시간의 최솟값을 출력한다.
예제 입력 1
2 6
7
10예제 출력 1
28예제 입력 2
7 10
3
8
3
6
9
2
4예제 출력 2
8문제 풀이
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class BJ3079 {
public static void main(String[] args) throws IOException {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st=new StringTokenizer(br.readLine());
long N=Long.parseLong(st.nextToken());
long M=Long.parseLong(st.nextToken());
long[] time=new long[(int)N];
long max=0;
long min=Long.MAX_VALUE;
for(int i=0;i<N;i++){
time[i]=Long.parseLong(br.readLine());
max=Math.max(time[i],max);
min=Math.min(min,time[i]);
}
long left=min;
long right=max*M;
while(left<=right){
long mid=(left+right)/2;
// 주어진 시간내에 처리할 수 있는 심사 인원
long cnt=0;
for(int i=0;i<N;i++){
cnt+=mid/time[i];
}
if(cnt<M){
left=mid+1;
}else{
right=mid-1;
}
}
System.out.println(left);
}
}M명의 인원이 N개의 입국심사대를 거쳐 모두가 심사를 마치는데에 필요한 시간의 최소값을 구하는 문제이다.
이분탐색을 이용하여 문제를 풀 수 있는데 심사를 마치는데에 필요한 시간을 탐색한다.
이분탐색의 특성상 시간을 탐색하고 일정 기준을 넘지 못하면 시간의 범위를 조정해가며 문제의 답을 찾아간다.
이때 기준을 어떤 것으로 잡을지가 관건이다.
특정 시간을 정했을 때, 각 입국 심사대에서 시간내에 처리할 수 있는 인원수를 체크하면 M명 넘게 처리할 수 있는지 아닌지에 따라 범위를 조정할 수 있다.
유의할 점
시간값/각 입국심사대에서 처리하는 시간값이 M을 넘기는지 아닌지에 따라 범위 조정- N과 M, T의 범위가 크기 때문에
long타입을 이용하여 문제를 푼다.
이분탐색
long left=min;
long right=max*M;
while(left<=right){
long mid=(left+right)/2;
// 주어진 시간내에 처리할 수 있는 심사 인원
long cnt=0;
for(int i=0;i<N;i++){
cnt+=mid/time[i];
}
if(cnt<M){
left=mid+1;
}else{
right=mid-1;
}
}
System.out.println(left);left는 입국심사대에서 걸리는 시간 중 최소값을, right는 가장 오래 걸리는 입국심사대에서 모든 인원이 처리할 때 걸리는 시간을 범위로 잡아 탐색을 진행한다.
이때, 위에서 설명한대로 mid 라는 시간 내에 각 입국심사대에서 처리할 수 있는 인원수를 체크하고 M보다 작다면 시간이 부족하다는 뜻이기 때문에 left 값을 조정하고
M보다 크거나 같다면 모든 인원을 시간내에 처리할 수 있는 상황이다. 이때, 시간의 최소값을 구하는 것이기 때문에 시간 범위를 줄여보기 위해 right 값을 조정한다.
모든 탐색이 끝나면 left 값이 right보다 커지기 때문에 left 값을 출력하면 된다.
처음에 left값을 max라고 잘 못 설정하고 풀었더니 예제문제를 계속 틀렸고 이후에는 long 타입 변수로 선언하지 않아 문제를 틀렸다.
이분탐색은 if문을 처리하고 난 뒤 어떤 값을 출력해야할지도 생각해봐야하고 범위 설정도 제대로 하지 않으면 틀리기 때문에 다른 문제보다 더 생각해야 할 것이 많은 것 같다.
