풀이
아이디어
문제를 처음 봤을 때는 그냥 단순하게 PriorityQueue를 이용해서 하나하나 빼서 해결하면 되지 않을까 생각하였습니다. 그러나 N이 2,000,000,000이고 M이 10,000이라는 점을 생각해보면 시간초과에 문제가 발생하리라 생각했습니다. 이에 생각의 전환이 필요로 했습니다.
문제의 분류를 보니 이분탐색이라고 적혀있는데 왜 이분탐색일까? 하고 역으로 생각해서 문제를 풀어보니 아이디어가 생각이 났습니다.
일정 T 시간이 주어졌을 때 얼마나 각 놀이기구에서 처리하는 사람의 수를 계산하면 어떻게 될까? 이를 풀어서 생각해보자
세부 설계
예제 입력을 예로 들어봅시다.
N = 7, M = 2
M1 = 3, M2 = 2
다음과 같이 주어졌을 때 시간의 최솟값은 0 그리고 최댓값은 M1과 M2 중에 큰 수 N으로 3 7인 21일 최댓값으로 잡았습니다.
L = 0, R = 21로 이분탐색을 시작합니다.
mid = 15입니다.
M1에서 처리하는 사람의 수는 15 / 3으로 5입니다.
M2에서 처리하는 사람의 수는 15 / 2로 7입니다.
하지만 우리는 0초 때부터 이미 한 사람이 들어갔다고 생각을 하므로 하나씩 더해줘야 합니다.
15 / 3 + 1;
15 / 2 + 1;
6 + 8로 14명이 처리되고 있음을 알 수 있습니다.
14 >= N(7)이기 때문에 R = mid - 1입니다.
L = 0, R = 14, mid = 7입니다.
M1에서 처리하는 사람의 수는 7/3 + 1로 3입니다.
M2에서 처리하는 사람의 수는 7/2 + 1로 4입니다.
우리는 7분이 되면 모든 줄이 비어있다는 사실을 알았습니다!
그러나 여기서는 마지막 아이가 타개되는 놀이기구의 번호를 알 수 없습니다. 그래서 저희는 마지막 아이가 놀이기구를 타게 되는 순간을 잡기 위해 계속 탐색을 진행합니다.
7 => 7이기 때문에 R = mid-1로 바꿔줍니다.
L = 0, R = 6, mid = 3입니다.
M1에서 처리하는 사람의 수는 3/3 + 1로 1입니다.
M2에서 처리하는 사람의 수는 3/2 + 1로 2입니다.
3 < 7이기 때문에 L = mid + 1로 바꿔줍니다.
L = 4, R = 6, mid = 5입니다.
M1에서 처리하는 사람의 수는 5/3 + 1로 3입니다.
M2에서 처리하는 사람의 수는 5/2 + 1로 3입니다.
6 < 7이기 때문에 L = mid + 1로 바꿔줍니다.
L = 6, R = 6, mid = 6입니다.
L == R이기 때문에 여기서 멈춥니다. 이제 우리는 결과적으로 처리하는 인원이 N이 되기 직전에 순간 즉 마지막 아이가 놀이기구에 탑승하는 순간을 알게 되었습니다.
이제 그렇다면 마지막 아이가 언제 탔는지를 배열을 돌면 됩니다.
시간이 6분일 때 M1은 6 % 3 == 0 이기 때문에 사람이 타고 있습니다.
시간이 6분일 때 M2는 6 % 2 == 0 이기 때문에 사람이 타고 있습니다.
둘 중에 어느 곳에 마지막 아이가 탔는지는 문제의 지문을 보면
만일 여러 개의 놀이기구가 동시에 비어 있으면, 더 작은 번호가 적혀 있는 놀이기구를 먼저 탑승한다고 한다.
이 부분을 통해 마지막을 나머지가 0인 기구에 탑승한다는 사실을 알게 됩니다!
이를 통해 문제를 해결할 수 있습니다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class No1561 {
static int N, M, max;
static int[] arr;
public static void main(String[] args) throws IOException {
input();
pro();
}
private static void pro() {
if(N <= M) {
System.out.println(N);
return;
}
long time = bsearch();
// System.out.println(time);
long cnt = M;
for(int i : arr)
cnt += (time-1)/i;
for(int i=0; i<M; i++) {
if(time % arr[i]==0) {
cnt++;
if(cnt == N) {
System.out.println(i + 1);
return;
}
}
}
}
private static long bsearch() {
long L = 0L;
long R = (long)max * N;
long result = -1;
while(L <= R) {
long mid = (L + R) / 2;
long child = 0;
for(int i : arr) {
child += mid / i;
child += 1;
}
if(child >= N) {
result = mid;
R = mid - 1;
}
else {
L = mid + 1;
}
}
return result;
}
private static void input() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
arr = new int[M];
max = 0;
st = new StringTokenizer(br.readLine());
for(int i=0; i<M; i++) {
arr[i] = Integer.parseInt(st.nextToken());
max = Math.max(arr[i], max);
}
br.close();
}
}
