[BOJ/C++] 1590 캠프가는 영식

시간 복잡도

• 버스의 개수 N이 최대 50, 운행하는 버스의 대수 C가 최대 100이므로
• $O(N*C)$의 시간으로 해결할 수 있습니다.

문제 접근법

• 버스의 시작 시각을 기준으로 간격마다 탐색을 진행합니다.
• 영식이의 도착시간보다 같거나 큰 버스의 출발 시간이 있다면 업데이트합니다.
• 각 버스의 종류마다 최솟값을 업데이트합니다.
• 만약 영식이가 도착한 시간 이후로 출발하는 버스가 없다면 정답을 -1로 업데이트합니다.

코드

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <string>
#include <climits>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>


using namespace std;

using int32 = long;
using int64 = long long;


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);


    int N, T, S, I, C;
    cin >> N >> T;

    int answer = INT_MAX;
    bool flag = false;

    for(int i=0; i<N; i++)
    {
        int waitTime = INT_MAX;
        cin >> S >> I >> C;

        for(int j=S; j<S+I*C; j+=I)
        {
	        if(j>=T)
	        {
                waitTime = j - T;
                flag = true;
                break;
	        }
                
        }
        answer = min(answer, waitTime);
    }

    if (!flag)
        answer = -1;
	
    cout << answer;


    return 0;
}