[99클럽 코테 스터디 18일차 TIL] 캠프가는 영식

 

 

 

오늘의 키워드

• 이진탐색

 

 

문제

 

영식이는 민식이와 함게 고속버스를 타고 캠프를 가야 하지만, 민식이는 영식이를 깨우지 않고 혼자 버스를 타고 캠프에 가버렸다.

영식이는 혼자 고속버스터미널까지 가서 캠프에 오려고 한다. 터미널에는 캠프 장소까지 운행하는 N가지의 버스가 있다. 각각의 버스는 시작 시각, 간격, 대수의 정보를 가지고 있다. 예를 들어, 어떤 버스의 시작 시각이 특점 시점을 기준으로 10분 후이고, 간격은 10분이고, 대수가 5대이면, 이 버스는 10분, 20분, 30분, 40분, 50분에 한 대씩 출발한다.

영식이는 버스터미널에 T분에 도착했다. 영식이가 버스를 타려면 최소 몇 분을 더 기다려야 하는지 구하는 프로그램을 작성하시오.

 

 

풀이

 

 

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

class Main {
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N, T;
        
        N = Integer.parseInt(st.nextToken());
        T = Integer.parseInt(st.nextToken());

        
        int min = 1000000;
        
        for(int i=0; i<N; i++){
            st = new StringTokenizer(br.readLine());
            int S = Integer.parseInt(st.nextToken());
            int I = Integer.parseInt(st.nextToken());
            int C = Integer.parseInt(st.nextToken());
            
            for(int j=0; j<C; j++){
                int arrival = S + I * j;
                
                if (arrival >= T) {
                    int wait = arrival - T;
                    min = Math.min(wait, min);
                    break;
                } 
            }
            
        }
        
        if(min == 1000000) {
            System.out.println(-1);
        } else {
            System.out.println(min);
        }
        
        
        
        
    }
}

 

 

 

이 방법은 이진탐색을 활용한 방법은 아니라서

이진탐색을 활용해서도 풀어보았다.

 

 

 

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

class Main {
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N, T;
        
        N = Integer.parseInt(st.nextToken());
        T = Integer.parseInt(st.nextToken());

       int min = 1000000; 
       
        
        for(int i=0; i<N; i++){
            st = new StringTokenizer(br.readLine());
            int S = Integer.parseInt(st.nextToken());
            int I = Integer.parseInt(st.nextToken());
            int C = Integer.parseInt(st.nextToken());
            
            int left = 0, right = C-1;
            int k = C;
            
            while(left <= right){
                int mid = (left+right)/2;
                int arrival = S + I * mid;
                
                if(arrival >= T){
                    k = mid;
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
            
            if (k < C) {
                int wait = (S + I * k) - T;
                min = Math.min(min, wait);
            }
            
        }
        
        if (min == 1000000) {
            System.out.println(-1);
        } else {
            System.out.println(min);
        }
        
    
        
    }
}

 

 

 

 

민식이는 앞으로 캠프갈 때 영식이 깨워서 가도록 ...