문제 개요
이 문제에서는 n개의 원소로 구성된 배열 arr[]와 정수 H가 주어집니다. 배열의 각 원소 arr[i]는 해당 사람이 처리해야 할 대기 중인 작업의 수를 나타내며, H는 모든 작업을 완료해야 하는 남은 시간(시간 단위)입니다. 우리의 목표는 모든 작업을 기한 내에 끝낼 수 있는 최소 작업 속도를 찾는 것입니다.
문제 설명
주어진 배열의 모든 작업을 H시간 안에 완료하기 위해 한 시간당 몇 개의 작업을 처리해야 하는지 구해야 합니다. 만약 arr[i]에 지정된 작업을 한 시간보다 빨리 끝낼 수 있다면, 남은 시간 동안은 쉬고 그 시간이 지난 후 다음 작업 세트로 넘어갑니다.
예제로 이해하기
입력:
arr[] = {4, 5, 1, 7, 8}, H = 5출력:
8
설명: 사람은 5시간 동안 5개의 작업 세트를 완료해야 합니다. 따라서 가장 많은 작업이 포함된 세트(8개)를 1시간 안에 처리할 수 있어야 하며, 이 값이 곧 필요한 최소 속도가 됩니다.
해결 접근 방법
이 문제를 해결하려면 모든 작업을 처리할 수 있는 최소 속도를 찾아야 합니다. 즉, 주어진 시간 안에 모든 작업을 완료할 수 있는 가장 작은 값을 찾으면 됩니다.
탐색 범위는 1부터 한 번에 처리할 수 있는 최대 작업 수까지입니다. 이 값이 매우 클 수 있으므로 계산 효율성을 위해 이진 탐색(Binary Search)을 사용합니다.
현재 속도 s로 작업을 완료할 수 있는지 확인하려면, 각 작업 세트를 완료하는 데 걸리는 시간을 구한 뒤 모든 세트의 시간을 합산합니다. 이 총 시간이 H 이하라면 해당 속도로 작업을 마칠 수 있고, 그렇지 않다면 더 빠른 속도가 필요합니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
bool canDoJobInTime(int A[], int n, int H, int speed) {
int timeTaken = 0;
for (int i = 0; i < n; ++i)
timeTaken += (A[i] - 1) / speed + 1;
return timeTaken <= H;
}
int calcJobMinSpeed(int A[], int n, int H) {
if (H < n)
return -1;
int maxJob = A[0];
for(int i = 1; i < n; i++)
maxJob = max(A[i], maxJob);
int start = 1, end = maxJob;
while (start < end) {
int mi = start + (end - start) / 2;
if (!canDoJobInTime(A, n, H, mi))
start = mi + 1;
else
end = mi;
}
return start;
}
int main() {
int A[] = { 3, 6, 7, 11 }, H = 8;
int n = sizeof(A) / sizeof(A[0]);
cout<<"The minimum speed to finish all jobs in time is "<<calcJobMinSpeed(A, n, H);
return 0;
}코드 설명
canDoJobInTime 함수: 각 작업 세트를 현재 속도로 처리할 때 걸리는 시간을 올림 나눗셈((A[i] - 1) / speed + 1)으로 계산하고, 총 소요 시간이 H 이하인지 판별합니다.
calcJobMinSpeed 함수: 먼저 H가 작업 세트 수 n보다 작으면 어떤 속도로도 불가능하므로 -1을 반환합니다. 이후 1부터 최대 작업 수까지의 범위에서 이진 탐색을 수행하여 조건을 만족하는 최소 속도를 찾습니다.
출력 결과
The minimum speed to finish all jobs in time is 4
시간 복잡도
각 속도 후보에 대해 배열 전체를 순회하므로 검증에 O(n)이 걸리고, 이진 탐색이 O(log M)(M은 최대 작업 수)번 수행되므로 전체 시간 복잡도는 O(n log M)입니다.