문제 탐색하기
입력 자료 정리
- n은 입국심사대의 개수, m은 대기줄에 있는 사람의 수다
- 이어서 들어오는 n개의 입력은 각 입국심사대별 소요시간이다
해결방법 추론
- 처음에는 문제를 읽고 그리디와 시뮬레이션을 생각하였다
- 하지만 입력값인 n의 크기를 보니 그 방법은 불가능할 것이라 생각하였고, 문제를 다시 읽게 되었다
- 결국 심사 받는데 걸리는 총 시간을 알게 되면 문제를 해결할 수 있으니까...
입국 심사가 걸릴 수 있는 범위 중 모든 사람을 통과시킬 수 있는
최소 값을 찾으면 되겠다고 생각하였다 - 그렇다면 할 수 있는 방법은 바로 이분탐색이다!
시간복잡도 계산
- 이분 탐색이 가능한지 시간복잡도를 계산해보았다
- 먼저 n만큼 어쨋든 탐색해야하므로, n만큼의 연산이 발생할 것이다
- 이어서 이분탐색을 해야하니 대상 범위의 최댓값인
max(Tk) x m에 log를 취한 log(max(Tk) x m)만큼의 연산이 발생할 것이다 - 따라서 시간복잡도는 O(n x log(max(Tk) x m))이며, 각 최대 입력값을 계산해보았을 때,
10^5 * 18 정도 이므로 시간제한 안에 문제를 해결할 수 있다!
코드 설계하기
변수 타입 설정
- 해당 문제에서는 범위를 보관하는 값을 제외하고는 모두 long 타입으로 지정하였다.
- 아무래도 m의 값이랑 Tk의 값이 크기 때문이고,
범위를 벗어나지 않는 몇 변수에 대해서도 범위를 벗어나는 값과의 연산이
존재하기 때문에 long타입으로 선언하였다
입력값 상태 관리하기
- n과 m은 변수로 저장하며, 들어오는 입력값들에 대해서는 모두 long타입의 배열에 저장한다
- 이분탐색을 위해서 입력 이후 배열을 오름차순 정렬해준다
좌우 값 설계하기
- left의 최소 범위는 1이 될 수 있다. 최소 시간이 1이기 때문이다
- 하지만 right는 단순히 Tk의 값만을 고려하면 안된다. m만큼의 사람이 몰려드는 것도 고려해야한다
- 따라서 right는 최댓값 Tk의 m만큼 곱한 값을 최대 범위로 갖게 된다
- 그리고 이 문제는 최솟값을 구해야하므로 출력을 위한 ans 변수에는 Long.MAX_VALUE로 초기화한다
이분탐색 설계하기
- 이분탐색의 범위는 심사하는데 걸리는 총시간이며,
여기서 찾고자 하는 값은 그 때 몇명의 사람을 받을 수 있고,
그 중 m을 넘기면서 가능한 최소 시간은 무엇인가? 이다 - 따라서 현재 범위의 중간값인 mid를 심사하는데 걸리는 총 시간으로 보면 된다
- 이어서 sum 변수를 하나 선언하고 n만큼 순회하면서 가능한 인원을 체크한다
- 각 심사대별로 mid에서 Tk를 나눈 몫을 sum에 더해준다.
이 값은 각 심사대에서 현재 총 심사하는데 걸리는 시간 중 가능한 인원이다 - 이제 이 sum을 가지고 m과 비교해서 범위를 조정한다
- 만약 sum이 m보다 크거나 같다면 일단 정답이 될 수 있는 후보이기 때문에
ans에 더 작은 값을 넣어준다 - 이어서 최솟값을 구하기 위해 right에 mid-1을 넘어 범위를 좁힌다
- 만약 작다면 정답 후보도 아니기 떄문에 left에 mid+1을 넣어 범위를 늘려준다
출력 설계하기
- 이분탐색 결과 완성한 ans를 출력하면 정답이 되는데..
시도회차 수정
1회차 시도 실패...
- 회차 시도 32%에서 틀려버렸다. 범위도 잘 지정했고, 정렬도 했고...
로직도 틀린게 없다고 생각했는데... 대체 왜 틀린 것일까? - 문제를 다시 읽어보고 틀린 부분이 놀랍게도 범위에서 발생할 수 있겠다는 것을 알게 되었다
- 자바에서 long타입의 범위가 대략 10^18 정도인데 m x Tk의 최댓값이 10^18이다..
- 이때 만약 Tk의 값 중에서 최댓값 하나만 10^9이고 나머지가 전부 1이라면...
첫 mid가 5^17일텐데 이 값을 (n-1)만큼 더할 수 있을 것이고, 그러면 10^18 범위를 벗어나게 된다! - 따라서 오버플로우가 발생할 것이고, 이 부분을 해결해주어야한다
- 그 방법으로 sum이 만약 m보다 크거나 같다면 break로 탈출하게 해주었다.
2회차 시도 성공!
- 해당 조건을 하나 추가하고 바로 성공하였다!
- 범위에 대해서 10^18승인 것을 보고 long타입으로 충분하겠다고 생각했는데,
이렇게 이분탐색 도중에 함정이 있을 줄은 꿈에도 몰랐다 - 만약 범위가 크고 아슬아슬하다면 오버플로우에 대한 고민을 깊게 하는 습관이 필요할 것 같다!
정답 코드
(1회차 시도 실패...)
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
long[] arr = new long[n];
long left = 0;
long right = 1;
for (int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(br.readLine());
right = Math.max(right, arr[i]*m);
}
long ans = Long.MAX_VALUE;
Arrays.sort(arr);
while(left <= right){
long mid = (left + right) / 2;
long sum = 0;
for (int i = 0; i < n; i++) {
long tmp = mid / arr[i];
sum += tmp;
}
if(sum >= m){
right = mid - 1;
ans = Math.min(ans, mid);
}else{
left = mid + 1;
}
}
bw.write(ans+"");
br.close();
bw.close();
}
}
(2회차 시도 성공!)
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
long[] arr = new long[n];
long left = 1;
long right = 1;
for (int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(br.readLine());
right = Math.max(right, arr[i]*m);
}
long ans = Long.MAX_VALUE;
Arrays.sort(arr);
while(left <= right){
long mid = (left + right) / 2;
long sum = 0;
for (int i = 0; i < n; i++) {
long tmp = mid / arr[i];
if(sum >= m){
break;
}
sum += tmp;
}
if(sum >= m){
right = mid - 1;
ans = Math.min(ans, mid);
}else{
left = mid + 1;
}
}
bw.write(ans+"");
br.close();
bw.close();
}
}
문제 링크
Software Developer