[알고리즘/C++] 작업 완료 최소 시간 구하기

한 Task를 처리하는데 각각 처리 시간이 다른 기계들이 있다. 

 

완료되어야 하는 작업의 수는 compNum개이고, 

 

각 기계들은 상이한 작업 처리 시간을 가지고 있다. 

 

compNum개의 작업이 모두 완료되기 위한 최소 시간은 얼마인가?

 

이진 탐색(binary search)를 통해서 구해보자. 

 

int minTaskTime(int taskNum, vi prcTime) {
	//taskNum: 해결해야하는 작업의 개수
	//prcTime: 작업하는 기계들의 처리시간을 갖는 벡터

	int low = 0;
	int high = 10000;
	int mid = 0;
	while (1) {
		int compNum = 0;
		mid = (low + high) / 2;
		for (int i = 0; i < prcTime.size(); i++) {
			compNum += floor(mid/prcTime[i]);
		}
		if (compNum == taskNum) {
			//mid 시간 동안 최대 완료할 수 있는 작업의 개수가
			//실제 달성해야하는 작업의 개수와 같다면 최적 해이다.
			return mid;
		}
		if (compNum > taskNum) {
			//완료 가능 작업 개수가 필요량보다 over하면
			//시간을 줄인다.
			high = mid;
		}
		else {
			low = mid;
		}
	}
}


int main() {
	vi arr = {135, 223, 311, 383};
	cout << minTaskTime(15, arr);
}