[SWEA] 3074 : 입국심사

https://swexpertacademy.com/main/talk/solvingClub/problemView.do?solveclubId=AV6kld8aisgDFASb&contestProbId=AV_XEokaAEcDFAX7&probBoxId=AV_W57U6ACQDFAX7&type=PROBLEM&problemBoxTitle=A%ED%98%95+%EC%A4%80%EB%B9%84+%EB%AC%B8%EC%A0%9C&problemBoxCnt=4 

SW Expert Academy

이분탐색을 이용해 푸는 문제였다.

기준 M을 두고 작으면 + 크면 - 하는 식이었는데 이분탐색을 이용해서 푸는 문제의 유형을 조금은 알 것 같다.

 

내 코드

메모리 : 57656 KB

시간 : 527 ms

코드길이 : 1585 B

 

[내 코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Solution {
	static int N;
	static int M;
	static int[] time;
	static long maxTime;
	static int result;

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;
		
		int T = Integer.parseInt(br.readLine());
		for(int t = 1; t <= T; t++) {
			sb.append('#').append(t).append(' ');
			st = new StringTokenizer(br.readLine());
			
			//심사대개수
			N = Integer.parseInt(st.nextToken());
			//대기인원
			M = Integer.parseInt(st.nextToken());
			maxTime = 0;
			time = new int[N];
			//심사대 소요시간 입력
			for(int n = 0; n < N; n++) {
				time[n] = Integer.parseInt(br.readLine());
				if(time[n] > maxTime)
					maxTime = time[n];
			}
			//이분탐색으로 최소시간 찾기
			sb.append(binarySearch(0, maxTime * M)).append('\n');
		}
		System.out.print(sb);
	}
	
	//소요시간 리턴
	public static long binarySearch(long start, long end) {
		//최소시간. 최악의 시간으로 초기화
		long result = maxTime * M;
		
		while(start <= end) {
			long person = 0;
			
			long mid = (start + end) / 2;
			for(int i = 0; i < N; i++) {
				person += mid / time[i];
			}
			
			//모자랄 때 --> 시간을 늘려야 함
			if(person < M) {
				start = mid + 1;
			}
			//초과할 때 --> 시간을 줄여야 함
			else {
				if(result > mid)
					result = mid;
				end = mid - 1;
			}
		}
		
		return result;
	}

}