[구름LEVEL] 소희와 버스

난이도	정답률
★★	62.7%

 

구름LEVEL

문제

소희=유치원생

유치원 정류장을 경우하는 N대가 있고, 각 버스마다 그 날의 최초 운행 시각 s와 정해진 루트를 돌고 다시 원위치로 오는 데 걸리는 시간 d가 있습니다. 

정류장에 가장 먼저 도착하는 버스를 타려고 합니다. 각 버스는 1번부터 N번까지 번호가 매겨져 있고, 만약 정류장에 가장 먼저 도착하는 버스가 여러 대라면 번호가 더 작은 버스를 탄다고 합니다.

소희가 정류장에 도착한 시각이 T일 때, 소희와 소희가 타게 될 버스는 몇 번인지 구해주세요.

 

해결

key point, 각 버스마다 도착시간이 T와 같거나 크게 되는 최초의 시각만 찾으면 된다.

1. i번째 버스의 최초 운행 시각 s와, 다시 정류장으로 돌아오게되는 시간 d를 arr[i]에 저장한다.
2. 1번 부터 N번 버스에 대해서 각 버스에 해당하는 d를 s에 더한다.
3. s가 소희가 정류장에 도착하는 시간인 t보다 크거나 같을 때까지 더해준다.
4. 그리하여 구해낸 i번째 버스가 T와 같거나 크게되는 최초의 시각을 몇 번째 버스인지 v배열에 pair로 저장하고
5. v배열을 정렬하여 v배열 첫 번째 인덱스에 있는 버스번호를 출력한다.

while문 안에 매번 v.push_back()을 이용하여 넣었다가 4번 테스트케이스에서 시간초과가 났었다. 사실상 while문 바깥으로 나왔을 때가 i번째 버스의 도착시간이 T와 같거나 크게 되는 최초의 시각이므로 while문 바깥으로 뺐더니 해결되었다. 앞으로도 유의하긔...

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int, int> p;
p arr[100005];
vector<p> v;
int n, t, ans;
int main() {
    scanf("%d %d", &n, &t);
    for (int i = 1, s, d; i <= n; i++) {
        scanf("%d %d", &s, &d);
        arr[i] = { s, d };
    }
    for (int i = 1; i <= n; i++) {
        while (arr[i].first < t) {
            arr[i].first += arr[i].second;
        }
        v.push_back({ arr[i].first, i });
    }
    sort(v.begin(), v.end());
    
    printf("%d", v[0].second);
    return 0;
}