[SWEA] 입국심사

Posted on | In |

문제 보러가기

제한사항

이외의 제한사항은 없다.

첫번째 생각

문제를 거꾸로 생각해서 심사가 끝나는 시간을 이분 탐색으로 찾아내면 된다.

count가 M 보다 작다면, 너무 작은 시간으로 잡은 것이고

count가 M보다 크거나 같다면, 너무 크게 잡은 것이다.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
import java.util.Scanner;

public class Solution {
    static int N,M;
    static int Im[];
    static long count=0;
    public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for(int tc=1;tc<=T;tc++) {
			N = sc.nextInt();
			M = sc.nextInt();
			Im = new int[N];
            for(int i = 0 ; i < N; i++) {
            	Im[i] = sc.nextInt();
            }
            count = 0;
            long start=1;
            long end = (long)Math.pow(10, 18);
            while(start<=end) {
                count = 0;
                long mid = (start+end)/2;
                for(int i = 0 ; i < N; i++) {
                    count+=(mid / Im[i]);
                }
                if(count < M) {
                    start = mid+1;
                }else {
                    end = mid-1;
                }
            }
            System.out.println("#"+tc+" "+start);
		}
	}
}