오늘을 배우고 내일을 개발하다

문제 링크 : https://www.acmicpc.net/problem/1590

[문제]

영식이는 민식이와 함께 고속버스를 타고 캠프를 가야하지만, 민식이는 영식이를 깨우지 않고 혼자 버스를 타고 캠프에 가버렸다.
영식이는 혼자 고속버스터미널까지 가서 캠프에 오려고 했다. 터미널에는 캠프 장소까지 운행하는 N가지의 버스가 있다. 각각의 버스는 시작 시각, 간격, 대수의 정보를 가지고 있다. 예를 들어, 어떤 버스의 시작 지점이 특정 시점을 기준으로 10분 후 이고, 간격은 10분이고, 대수가 5대이면, 이 버스는 10분, 20분, 30분, 40분, 50분에 한 대씩 출발한다.
영식이는 버스터미널에 T분에 도착했다. 영식이가 버스를 타려면 최소 몇 분을 더 가야하는지 구하는 프로그램을 작성하시오.

[입력]

첫째 줄에 버스의 개수 N과 영식이가 버스터미널에 도착하는 시간 T가 주어진다. 둘째 줄부터 총 N개의 줄에 각 버스의 시작 시각 Si, 간격 Ii, 대수 Ci가 공백을 사이에 두고 주어진다.

[출력]

첫째 줄에 영식이가 기다려야하는 시간을 출력한다. 영식이가 도착하는 동시에 버스가 출발하면 정답은 0 이다.

만약 버스가 없어서 캠프에 갈 수 없으면 -1을 출력한다.

정답은 231보다 작다.

[제한]

• 0 ≤ 50
• 1 ≤ T ≤ 1,000,000
• 1 ≤ Si ≤ 1,000,000
• 1 ≤ Ii ≤ 10,000
• 1 ≤ Ci ≤ 100

[알고리즘 분류]

• 수학
• 이분 탐색
• 브루트포스 알고리즘

[해설]

이 문제에서 원하는 것은 영식이가 터미널에 도착하는 시간 T보다 큰 수 중에서도 가장 작은 값을 구하는 것이라고 할 수 있다.
답을 구하기 위해서는 버스가 처음 출발하는 시간과 간격, 대수를 이용해 버스를 운행하는 모든 시간을 구하고 이를 배열에 저장하여 정렬한다.
그리고 반복문을 통해 순회하면서 처음으로 T보다 큰 값을 찾아 그 수에서 T를 뺀 값을 출력하면 된다.
또, 영식이가 탈 수 있는 버스가 존재하지 않는 것을 알기 위해서는 정렬한 후에 배열의 끝 값을 T와 비교했을 때 T가 배열의 끝 값도가 크지 않다면 영식이가 탈 수 있는 버스가 존재하지 않는 것이므로 -1을 출력하면 된다.

[정답 코드]

#include <bits/stdc++.h>
using namespace std;
int N,T,S,I,C;
vector<int> b;

int main() {
  cin >> N >> T;
  while(N--){
    cin >> S >> I >> C;
    for(int i=0;i<C;i++) b.push_back(S+(I*i));
  }
  sort(b.begin(),b.end());
  if(b[b.size()-1]<T) cout << "-1";
  else {
    for(int i=0;i<b.size();i++) if(b[i]>T){
      cout << b[i]-T;
      break;
    }
  }
}

[결과]