문제

입국 심사

풀이

최대 10억개를 최대 10만번 비교해야 함으로 bruteforce는 애초에 시간초과입니다. 이분탐색에 경우에는 확실히 한번에 이분탐색으로 풀어야 한다라는 생각을 하지못한다. 그냥 애초에 bruteforce를 이분탐색으로도 풀어보면 괜찮을것같다는 생각이..

상근이와 친구들이 심사를 받는데 이분탐색으로 구하기 전 시간의 최소값과 최대값을 구해야 한다.

for (int i = 0; i < n; i++) {
	...
	min = Math.min(min, station[i]);
    max = Math.max(max, station[i]);
}

// 모든 인원이 가장 긴 시간이 걸리는 입국 심사대에 있을경우
max *= m;

최소값의 경우에는 상근이와 친구들이 1명이 최소로 들어가기 때문에 배열중 최소값으로 구현한다.

while (min <= max) {
	long mid = (min + max) / 2;
    
    long count = 0;
    for (int i = 0; i < n; i++) {
    	count += mid / station[i];
    }
    
    if (count < m) {
    	min = mid + 1;	
    } else {
    	max = mid - 1;
    }
}

이때 자료형은 long으로 두어야 한다. 이것땜에 몇번을 틀렸나.. ;;
그런데도 계속 틀렸음. 그래서 결국 질문게시판 들락날락했더니..for문 안에있는 count가 m을 초과할경우 탈출해주어야 시초가 안난다고 한다.. 주륵

...
for (int i = 0; i < n; i++) {
	count += mid / station[m];
    if (count > m) { break; } // 추가 해줌
}
...

아니 테스트케이스가 좀 변경이 된건지.. 구글링을 해봐도 break까지 구현해 놓은 코드가 없다.

전체 코드

전체 코드