[BOJ 19592 // C++] 장난감 경주

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 19592번 문제인 장난감 경주이다.
문제는 아래 링크를 확인하자.

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

 

단독 우승만을 목표로 하는데 다른 참가자의 자동차들은 일정한 속력으로 이동하므로, 다른 참가자의 자동차는 가장 빠른 속력을 가진 것만을 신경써도 충분하다. 해당 차와의 비교만을 생각하자.

 

먼저, 부스터를 사용하지 않은 상태로도 상대 차를 앞설 수 있는 경우 답은 0이 된다.

 

그렇지 않을 경우 문제의 답은 $Y$ 이하의 각 부스터속도에 대하여 상대 차를 앞설 수 있는 $Y$가 있을 경우 그 최솟값, 그렇지 않을 경우 -1이 된다.

 

가능한 $Y$의 후보는 많아야 100만개이고, 테스트케이스도 많아야 10개이므로 가능한 모든 $Y$값을 확인해 문제를 해결하자.

 

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;
typedef long long ll;

ll N, X, Y;
ll V, VV;

void solve() {
	V = 0;
	cin >> N >> X >> Y;
	for (int i = 1; i < N; i++) {
		ll v; cin >> v;
		V = max(V, v);
	}

	cin >> VV;
	if (V < VV) cout << 0 << '\n';
	else {
		for (ll v = VV + 1; v <= Y; v++) {
			ll d = X - V, dd = X - v;
			if (d * VV > dd * V) {
				cout << v << '\n';
				return;
			}
		}

		cout << -1 << '\n';
	}
}

int T;

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

	cin >> T;
	while (T--) solve();
}