AlgoSpot) CANADATRIP

문제 : https://algospot.com/judge/problem/read/CANADATRIP

N개의 도시가 있는데 도시 M[i]미터 전부터 표지판이 세워지고 G[i]미터 간격으로 표지판이 세워진다. 이때 K번째 표지판의 위치를 구하는 문제이다.

이 문제또한 결정문제로 바꿔서 풀경우 빠르게 풀수 있습니다.

이분법을 이용해서 K개 이상의 표지판을 포함하는 거리를 좁혀나가면서 K개의 표지판을 포함하는 거리를 찾았습니다.

#include 
#include 
#include 

using namespace std;

int N, K;

int L[5000], M[5000], G[5000]; // 시작점부터 도시의 거리, (표지판이)몇미터부터, (표지판이)몇미터 간격

bool decision(int dist) {
	int check = 0;

	for (int i = 0; i < N; ++i)
		if (dist >= L[i] - M[i]) check += (min(dist,L[i]) - (L[i] - M[i])) / G[i] + 1;
	
	return (check >= K);
}
int optimize() {
	int lo = -1, hi = 8030001;

	while(lo + 1 < hi){
		int mid = (lo + hi) / 2;

		if (decision(mid)) {
			hi = mid;
		}
		else {
			lo = mid;
		}
	}

	return hi;
}
int main() {
	std::ios::sync_with_stdio(false);
	freopen("test.txt", "r", stdin);
	int C;
	cin >> C;

	while (C--) {
		memset(L, 0, sizeof(L));
		memset(M, 0, sizeof(M));
		memset(G, 0, sizeof(G));

		cin >> N >> K;

		for (int i = 0; i < N; ++i) {
			cin >> L[i] >> M[i] >> G[i];
		}
		
		cout << optimize() << endl;
	}
	return 0;
}