백준 1590번: 캠프가는 영식

버스 정류장에 도착한 시간 T 이후에 가장 빨리 출발하는 버스를 찾는 문제다.

문제 설명

• 기준 시점: 영식이가 도착하는 시간 T

• 버스 정보: 각 버스 노선은 시작 시간(S), 간격(I), 대수(C)를 가진다.

• 모든 노선의 모든 버스 시각 중 T 이상인 값 중 가장 작은 값을 찾아
  T와의 차이를 구하는 것.

입력 값

• 첫째 줄에 노선의 종류(우등, 일반 느낌) N개, 버스터미널에 도착하는 시간 T

• 둘째 줄에는 버스 개수 N개에 대한 각 버스의 시작 시간, 간격, 대수가
  공백을 사이에 두고 주어진다.

출력 값

• 영식이가 기다려야 하는 시간을 출력한다.
  • 추가적으로 영식이가 도착하는 동시에 버스가 출발하면 0,
  • 만약 버스가 없어서 캠프에 갈 수 없으면 -1

• 하나의 버스 노선(S, I, C)에 대해 영식이가 탈 수 있는 가장 빠른 버스 시각 구하기
  1. 영식이가 첫 차보다 빨리 온 경우 ( T ≤ S )
     • 가장 빨리 탈 수 있는 차가 당연히 첫 차인 S이다.
     • 기다리는 시간: (S - T)
       
       
  2. 영식이가 마지막 차보다 늦게 온 경우 ( T > S + (C-1)I )
     • 이 노선에는 탈 수 있는 버스가 없다.
       
       
  3. 영식이가 운행 기간 중에 온 경우 ( S < T ≤ S + (C-1)I )
     • 시작 시간인 S 시점부터 T까지 흐른 시간은 (T - S)
     • 이 시간 동안 버스 간격 I가 몇 번 지났는지 계산해야 한다.
       (T - S) / I
     • 이를 토대로 현재 노선에서 기다려야 하는 시간도 구한다.

  • 전체 버스 노선 중 최소값 갱신

    모든 노선에 대해 위 과정을 반복하며 가장 작은 기다리는 시간을 저장한다.

    • 초기값 설정: 최소 대기 시간을 저장할 변수를
      아주 큰 값(예: Integer.MAX_VALUE)으로 초기화한다.
      
      
    • 유효성 검사: 만약 어떤 버스 노선에서도 탈 수 있는 버스가 없다면
      (즉, 초기값이 변하지 않았다면) 1을 출력한다.

  • 왜 마지막 버스인데 C-1 이냐하면

    • C: 버스의 총 대수 (예: 3대)

    • I: 버스 사이의 시간 간격 (예: 10분)

    • S: 첫 번째 버스가 출발하는 시각 (기준점)

    • 버스가 3대(C=3) 있다고 가정하고 시간을 계산

    1. 첫 번째 버스 (1번): 그냥 시작 시간 S에 출발한다. (간격 I를 더할 필요가 없음)

    2. 두 번째 버스 (2번): S에서 간격 I가 1번 지났을 때 출발한다. (S + 1 x I)

    3. 세 번째 버스 (마지막 버스): S에서 간격 I가 2번 지났을 때 출발한다.
       (S + 2 x I)

       버스가 3대(C=3)일 때 마지막 버스의 시각을 구하기 위해
       간격 I를 곱한 횟수는 2번이다. 즉, 3 - 1번
       

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

public class test1590 {

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    StringTokenizer st = new StringTokenizer(br.readLine());

    // 버스 종류 개수 (우등인지 일반인지)
    int N = Integer.parseInt(st.nextToken());

    // 영식이가 버스 터미널에 도착할 시간
    int T = Integer.parseInt(st.nextToken());

    // 결과값 저장 (초기값: -1, 버스가 없는 경우 대비)
    long minWait = -1;

    for (int i = 0; i < N; i++) {
      st = new StringTokenizer(br.readLine());
      long S = Integer.parseInt(st.nextToken()); // 시작 시간
      long I = Integer.parseInt(st.nextToken()); // 간격
      long C = Integer.parseInt(st.nextToken()); // 대수

      // 해당 버스 노선의 마지막 차 시간 계산
      long lastBusTime = S + (C - 1) * I;

      // 영식이가 마지막 차보다 늦게 오면 이 노선은 당연히 놓치는 것이다.
      if (T > lastBusTime) continue;

      long nextBusTime;

      // 영식이가 첫 차보다 빨리 온 경우
      if (T <= S) {
        nextBusTime = S;
      } else {
        // 첫 차 이후에 도착한 경우 -> 몇 번째 차를 탈 수 있는지 계산
        // (T인 도착시간 - S인 시작시간)을 간격 I로 나눈 몫으로 이미 지나간 차의 대수 파악
        // 예로 50이라는 시간에 도착했고 시작 시간인 S는 30이라면 50 - 30 = 20
        // 20이라는 시간이 지나간 것이고 이 20이라는 시간동안 몇 대가 지나갔는지 확인하려면
        // 당연히 간격인 I로 나눈 몫을 통해 확인할 수 있다. 
        // (간격이 10이면 20 / 10 -> 2대 지나간 것)
        // ceil로 올림 처리
        int goneBusCount = (int) Math.ceil((double) (T - S) / I);
        nextBusTime = S + goneBusCount * I;
      }

      // 현재 노선에서 기다려야 하는 시간
      long currentWait = nextBusTime - T;
      
      // 전체 노선 중 최소값 갱신
      if (minWait == -1 || currentWait < minWait) {
        minWait = currentWait;
      }
    }

    System.out.println(minWait);
  }

}