(C++) - 백준(BOJ) 1590번 : 캠프가는 영식 답

www.acmicpc.net/problem/1590

1590번: 캠프가는 영식

예외경우 처리가 중요했던 완전탐색 문제였습니다.

 

풀이방법

1. 유효한 버스 도착시간의 범위(남은시간) : 영식의 도착시간 - 버스 출발시간 

    x번째 버스 = 남은시간 / 배차간격 , 나머지가 0이면 그대로 적용 : 나머지가 0이 아니면 +1을 적용

 

2. 남은시간이 음수라면 버스타지 못하므로 x번째 버스는 0

 

3. 영식의 도착시간보다 늦게 도착하는 버스의 도착시간 : 버스 출발시간 + 배차 * x번째버스

 

4. x번째버스가 버스개수 미만이라면 답을 구합니다.

   답 = min(답, 3번에서 구한 시간 - 영식도착시간)

Code

 

#include <bits/stdc++.h>
using namespace std;
int waitTime = 0x7f7f7f7f;
struct Bus{ int startTime, gapTime, busCount; };
Bus busInfo[100000];
int main(){
    int n;
    int goal;
    cin >> n >> goal;
    for(int i = 0; i < n; i++){
        cin >> busInfo[i].startTime >> busInfo[i].gapTime >> busInfo[i].busCount;
    }
    
    for(int i = 0; i < n; i++){
        int startTime = busInfo[i].startTime;
        int gapTime = busInfo[i].gapTime;
        int leftTime = goal - startTime;
        int nthBus = leftTime % gapTime <= 0 ? (leftTime / gapTime) : (leftTime / gapTime + 1);
        if(nthBus < 0) nthBus=0;
        int arriveTime = startTime + gapTime * nthBus;
        if(nthBus < busInfo[i].busCount) 
            waitTime = min (waitTime,arriveTime - goal);
    }
    if(waitTime == 0x7f7f7f7f) cout << "-1";
    else cout << waitTime << '\n';
}