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

https://www.acmicpc.net/problem/1590

1590번: 캠프가는 영식

 

풀이

처음에 모든 버스의 도착시간 배열을 만들까 하다가 입력 + 정렬 등등 코드가 너무 복잡해질 것 같아서 

각 버스 별로 기다리는 최소 시간을 이분 탐색으로 찾아주었다.

 

left = 첫번째 버스, right 는 마지막 버스로 입력 받고

is_possible 함수에서 시간 계산을 해주고 영식이가 도착한 시간 이후로 버스가 도착해야 탈 수 있기 때문에 T보다 큰 mid(버스)를 반환해주었다.

 

그리고 ret 에는 (mid 버스의 시간 - T) 의 계산한 값을 입력, 최솟값을 갱신해가면서 전체 버스 중에 가장 짧게 기다리는 시간을 출력해주었다.

 

 

전체 코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int N, T;
int S, I, C;
int ret = -1;
int tmp = 987654321;

bool is_possible(int mid) {
	if (S + I * (mid - 1) >= T) return true;
	return false;
}

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

	cin >> N >> T;

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

		int left = 1, right = C; //시작지점부터 최대지점까지

		while (left <= right) {
			int mid = (left + right) / 2;
			if (is_possible(mid)) {
				ret = (S + I * (mid - 1)) - T;
				ret = min(tmp, (S + I * (mid - 1)) - T);
				tmp = ret;
				right = mid - 1;
			}
			else left = mid + 1;
		}
	}

	cout << ret;
}