1590_캠프가는 영식

사용 알고리즘: 이분 탐색

사용 언어: java

 

각 버스마다 list를 만들어서, 버스 이용 가능 시간을 만들고 -> 이분탐색

(이분탐색의 결과 - 영식이 도착 시간) 중 가장 작은 수를 계속 갱신

 

이분탐색은: 

도착시간보다 "크거나 같은" 수 중, 가장 작은 수가 나와야 함.

즉, while 문은 left==right까지도 확인을 해야 하고, 영식이 도착 시간과 딱 맞는 시간이 없다면 

이분탐색은 결국 right가 left보다 이전을 가리키는 것으로 끝날 것이기 때문에, 

left가 도착시간보다 "크거나 같은" 수 중, 가장 작은 수

 

package week21;

import java.io.*;
import java.util.*;

public class Main {

	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();//버스개수
		int 도착시간 = sc.nextInt(); //!
		int min = Integer.MAX_VALUE;
		
		int[][] buses = new int[n][3]; //시작시간, 간격, 대수
		for(int i=0; i<n; i++) {
			for(int j=0; j<3; j++) {
				buses[i][j] = sc.nextInt();
			}
		}
		
		for(int[] bus : buses) {
			List<Integer> bu = new ArrayList<>(); //이걸로 이분탐색
			for(int i=0; i<bus[2]; i++) {
				bu.add(bus[0] + bus[1] * i); 
			}
			
			int left = 0;
			int right = bus[2] - 1;
			while(left <= right) {
				int mid = (left+right )/2;
				
				if(bu.get(mid) == 도착시간) {
					min = 0;
					break;
				}
				else if(bu.get(mid) < 도착시간) {
					left = mid + 1;
				}
				else {
					right = mid - 1;
				}
			}
			
			if (min == 0)
				break;
			
			//left가 큰 수 중 가장 작은 수;
			if(left < 0 || left >= bus[2]) continue;
			min = Math.min(min, bu.get(left) - 도착시간);
		}
		
		//
		if(min != Integer.MAX_VALUE) System.out.println(min);
		else System.out.println(-1);
	}

}