[BOJ] 1590 - 캠프가는 영식

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다.

 

문제 설명

www.acmicpc.net/problem/1590

1590번: 캠프가는 영식

난이도: 실버 1

사용언어: JAVA

 

영식이는 버스를 타야합니다. 버스터미널에는 N개의 종류의 버스가 존재하고, 영식이가 버스터미널에 도착한 시간은 T입니다. 각각의 버스는 첫 차 시간, 간격, 총 대수의 정보를 가지고 있습니다. 만일 버스에 대한 정보가 150 50 10으로 주어진다면, 해당 버스의 첫 차 시간이 150이고, 50분 간격으로 출발하며, 총 10대가 존재한다는 뜻입니다.

 

이 때, 영식이가 버스를 타기위해 기다려야 하는 최소 시간을 구하는 문제입니다.

 

풀이

이 문제는 문제 파악과 예외 처리만 잘 해주면 쉽게 풀 수 있습니다. 우선 영식이가 도착한 시간을 기점으로 각각의 버스에는 두 가지 경우의 수가 존재합니다.

 

1. 버스 첫 차 시간이 영식이가 도착한 시간보다 늦는 경우

2. 버스 첫 차 시간이 영식이가 도착하기 전인 경우

 

첫 번째 경우에 영식이가 해당 버스를 타기 위해 기다려야하는 최소 시간은 첫 차 시간으로부터 영식이가 도착한 시간을 빼준 값입니다. 그리고 두 번째 경우에는 첫 차 시간으로부터 간격 시간을 총 대수동안 반복하며 더해주면 됩니다. 더해주다가 영식이가 도착하는 시간보다 값이 커지는 경우, 더하기를 멈추고, 해당 시간에서 영식이가 도착할 시간을 빼주기만 하면 됩니다.

 

이 과정을 버스의 종류의 수인 N번 반복하며 최소값을 업데이트 해주면 됩니다. 그리고 어떤 경우에도 영식이의 도착시간보다 늦게 출발하는 버스가 없는 경우에는, 위의 과정에서 최소값을 한 번도 업데이트 하지 못하기 때문에, 코드의 마지막에서 -1을 출력하도록 예외 처리만 해주면 됩니다.

 

이렇게 모든 경우의 수를 그냥 무식하게 다 계산하는 방법을 브루트포스라고 하죠.

 

import java.io.*;
import java.util.StringTokenizer;
 
 
class Main {
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        int N, T;
        int time, interval, number;
        int min = 1000000000;
        String s = br.readLine();
        StringTokenizer st = new StringTokenizer(s);
        N = Integer.parseInt(st.nextToken());
        T = Integer.parseInt(st.nextToken());
 
        int i, j;
        for (i = 0; i < N; i++) { // 버스의 종류 N개 동안 반복
            s = br.readLine();
            st = new StringTokenizer(s);
            time = Integer.parseInt(st.nextToken());
            interval = Integer.parseInt(st.nextToken());
            number = Integer.parseInt(st.nextToken());
 
            if (time >= T && min > (time - T)) { // 만약 영식이가 도착하는 시간보다 해당 버스의 첫 차 시간이 더 늦으면
                min = time - T; // 기존의 min 값 보다 작으면 min을 업데이트
            }
            else{ // 영식이의 도착 시간보다 첫 차 시간이 이른 경우
                for(j=0;j<number;j++){ // 총 대수 만큼 반복
                    if(time >= T){ // 영식이의 도착시간보다 늦게 출발하는 버스가 있으면,
                        if(min > (time - T)) { // 기존의 min 값 보다 작다면?
                            min = time - T; // min 값을 업데이트
                        }
                        break;
                    }
                    time += interval; // 첫 차 시간에 계속 간격만큼의 시간을 더해줌
                }
            }
        }
 
        if(min == 1000000000) // min 값이 한번도 업데이트 되지 못했다면
            System.out.print(-1);
        else
            System.out.print(min);
    }
}