[백준 1590번] 캠프가는 영식 (C++)

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

1590번: 캠프가는 영식

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int N, T, a, b, c, result = -1;

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    cin >> N >> T;
    int minV = 1000000;

    for(int i=1; i<=N; i++) 
    {
        cin >> a >> b >> c;
        int tmp = a; //시작점
        for(int j=1; j<=c; j++)
        {
            if(tmp >= T) 
            {
                result = tmp-T;
                break;
            }
            tmp += b; //다음 버스
        }
        if(result==-1) continue; //-1은 불가능한 경우이므로 스킵
        minV = min(result, minV); //최솟값 저장
    }
    cout<< ((result==-1) ? -1 : minV);



    return 0;
}

 

태그에 이분탐색이 있지만, 범위가 크지않아 단순계산으로도 풀이가 가능한 문제이다.

현재 시작점을 기준으로 가능한 대수 만큼 간격을 하나씩 더해준다.

이렇게 더해준 값이 터미널 도착시간인 T보다 크거나 같아야 탑승 또는 기다림이 가능하다.

T보다 크거나 같아지는 경우에 시작점 + 누적된 간격의 값에 T를 빼서 남은 기다림 시간이 몇인지를 구해준다.

 

케이스가 여러가지이므로 위 과정을 반복하며 최솟값을 구해준다.

이때 주의해야 할 것은 -1은 불가능한 수치를 나타내기위해 초기화를 -1로 해준 것이므로, result 값이 -1 그대로라면 불가능한 경우이기에 이 경우엔 최솟값 갱신을 스킵해준다.