#1590 : 캠프가는 영식

풀이방법

사용된 것:

브루트포스 알고리즘

 

2022.06.19

브루트포스로 풀면 매우 쉽다. 굳이 이분 탐색을 써보려고 하다가 계속 실수를 해서 그냥 브루트포스로 풀었다.

 

각 버스 노선마다,

영식이의 터미널 도착 이후에 출발하는 배차들 중 가장 이른 것 하나만 다룬다.

이 조건을 만족하는 버스 출발 시간은 각 노선마다 1개 혹은 0개 있다. 이렇게 찾아낸 출발 시간들 중 최솟값을 취하면 된다.

 

영식이의 터미널 도착 이후에 출발하는 배차가 하나도 없을 때, 즉 영식이가 탈 수 있는 버스가 없을 때는 화면에 -1을 출력한다.

 

코드

Java(2022.06.19)

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

public class Main {

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		//N과 T 읽어오기
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int t = Integer.parseInt(st.nextToken());
		
		long min = Long.MAX_VALUE;	//영식이가 탈 가장 이른 버스의 출발시간을 저장할 변수
		boolean check = false;	//영식이가 탈 수 있는 버스의 존재여부를 기록할 변수
		
		//각 노선의 정보를 읽어와 점검
		for(int i=0; i<n; i++) {
			st = new StringTokenizer(br.readLine());
			long s = Integer.parseInt(st.nextToken());
			long gap = Integer.parseInt(st.nextToken());
			long c = Integer.parseInt(st.nextToken());
			for(int j=0; j<c; j++) {
				//각 노선마다, 영식이의 터미널 도착 이후이면서 가장 이른 배차를 점검
				long num = s + (j*gap);
				if(num>=t) {check = true; min = Math.min(min, num); break;}
			}
		}
		
		//정답 출력
		if(check) System.out.print(min-t);	//영식이가 탈 수 있는 버스가 존재할 경우
		else System.out.print(-1);	//그렇지 않은 경우
	}

}