C++에서 주어진 제약 조건 아래 모든 작업을 완료하는 최소 시간 찾기

개요

서로 다른 소요 시간을 가진 작업 배열이 주어지고, 동일한 능력을 지닌 k명의 작업자(할당자)가 사용 가능하며, 각 작업자가 작업 1단위를 처리하는 데 걸리는 시간 t도 함께 주어집니다. 이때 다음 두 가지 제약 조건을 만족하면서 모든 작업을 완료하는 데 필요한 최소 시간을 구하는 것이 문제의 목표입니다.

첫 번째 제약 조건: 한 작업자에게는 반드시 연속된 작업만 할당할 수 있습니다. 예를 들어 배열에서 위치 1과 2의 작업은 같은 작업자에게 배정할 수 있지만, 위치 1과 3처럼 떨어진 작업은 배정할 수 없습니다.
두 번째 제약 조건: 두 명의 작업자가 하나의 작업을 나누어 수행할 수 없습니다. 즉, 하나의 작업이 여러 작업자에게 부분적으로 분배되는 일은 없어야 합니다.

입력 형식

k — 사용 가능한 작업자의 수
t — 작업자가 작업 1단위를 완료하는 데 걸리는 시간
JOB[] — 각 작업의 소요 시간을 나타내는 배열

예제

예제 1

k = 2, t = 4, JOB[] = {5, 6, 12}

출력: 48

사용 가능한 작업자는 2명입니다. 첫 번째 작업자에게 {5, 6}(총 11단위)을, 두 번째 작업자에게 {12}(12단위)를 할당하면 각각 44와 48의 시간이 걸리며, 전체 완료 시간은 이 중 최대값인 48이 됩니다.

예제 2

k = 4, t = 5, JOB[] = {12, 6, 9, 15, 5, 9}

출력: 75

{12}, {6, 9}, {15}, {5, 9}의 네 그룹으로 나누어 각 작업자에게 하나씩 할당합니다. 각 그룹의 단위 합은 12, 15, 15, 14이고, 여기에 t = 5를 곱하면 최대 75가 되므로 정답은 75입니다.

접근 방법: 이진 탐색 + 그리디

이 문제의 핵심 아이디어는 이진 탐색(Binary Search)입니다. 먼저, 주어진 시간 안에 사용 가능한 작업자 수로 모든 작업을 끝낼 수 있는지 판별하는 함수 isPossible()이 있다고 가정해 보겠습니다. 이 함수가 있다면 정답(최소 시간)에 대해 이진 탐색을 수행할 수 있습니다.

탐색 범위의 하한은 0으로 설정할 수 있고, 실질적으로는 가장 오래 걸리는 작업 하나의 시간보다 작을 수 없습니다(작업을 분할할 수 없기 때문).
탐색 범위의 상한은 모든 작업 시간의 합입니다(작업자가 충분하다면 이 시간 안에 반드시 완료 가능).
중간값(mid)으로 작업 완료가 가능하면 더 작은 시간을 찾기 위해 왼쪽 절반을 탐색하고, 불가능하면 오른쪽 절반을 탐색합니다.

그렇다면 isPossible()은 어떻게 구현할까요? 여기서는 그리디(Greedy) 접근을 사용합니다. 모든 작업을 순서대로 살펴보면서 현재 작업자에게 하나씩 누적 배정하고, 현재 작업자의 누적 시간이 주어진 시간 한도를 초과하면 새로운 작업자를 만들어 배정을 계속합니다. 이 과정에서 필요한 작업자 수가 k를 초과하면 false를, 그렇지 않으면 true를 반환합니다.

C++ 구현 예제

// C++ 프로그램: 주어진 수의 작업자로 모든 작업을 완료하는 최소 시간 찾기
#include<bits/stdc++.h>
using namespace std;

// 배열 arr1[0..n1-1]에서 최댓값을 구하는 유틸리티 함수
int getMax(int arr1[], int n1){
    int result1 = arr1[0];
    for (int i=1; i<n1; i++)
        if (arr1[i] > result1)
            result1 = arr1[i];
    return result1;
}

// job1[]의 모든 작업을 주어진 시간 'time1' 안에 끝낼 수 있으면 true 반환
bool isPossible(int time1, int K1, int job1[], int n1){
    // cnt1: 현재까지 필요한 작업자 수
    int cnt1 = 1;
    int curr_time1 = 0; // 현재 작업자에게 할당된 시간
    for (int i = 0; i < n1;){
        // 현재 작업자의 누적 시간이 한도를 초과하면 새 작업자 추가
        if (curr_time1 + job1[i] > time1) {
            curr_time1 = 0;
            cnt1++;
        }
        else { // 그렇지 않으면 작업 시간을 누적하고 다음 작업으로 이동
            curr_time1 += job1[i];
            i++;
        }
    }
    // 필요한 작업자 수가 k 이하이면 true
    return (cnt1 <= K1);
}

// 주어진 작업 배열을 완료하는 데 필요한 최소 시간 반환
// K1 --> 작업자 수
// T1 --> 각 작업자가 1단위를 처리하는 데 걸리는 시간
// n1 --> 작업의 개수
int findMinTime(int K1, int T1, int job1[], int n1){
    // 이진 탐색의 시작(start1)과 끝(end1) 설정
    // end1은 시간의 상한 역할을 함
    int end1 = 0, start1 = 0;
    for (int i = 0; i < n1; ++i)
        end1 += job1[i];
    int ans1 = end1; // 답 초기화
    // 가장 오래 걸리는 작업의 시간 확인
    int job_max1 = getMax(job1, n1);
    // 최소 실현 가능 시간에 대해 이진 탐색 수행
    while (start1 <= end1){
        int mid1 = (start1 + end1) / 2;
        // mid 시간 안에 작업 완료가 가능한 경우
        if (mid1 >= job_max1 && isPossible(mid1, K1, job1, n1)){
            ans1 = min(ans1, mid1); // 답 갱신
            end1 = mid1 - 1;
        }
        else
            start1 = mid1 + 1;
    }
    return (ans1 * T1);
}

// 드라이버 프로그램
int main(){
    int job1[] = {12, 6, 9, 15, 5, 9};
    // int job1[] = {5, 6, 12};
    int n1 = sizeof(job1)/sizeof(job1[0]);
    int k1=4, T1=5;
    // int k1=2, T1=4;
    cout << findMinTime(k1, T1, job1, n1) << endl;
    return 0;
}

출력

복잡도 분석

이진 탐색은 최대 O(log S)(S는 모든 작업 시간의 합)번 반복되며, 각 반복마다 isPossible()이 모든 작업을 한 번씩 훑으므로 O(n)의 시간이 걸립니다. 따라서 전체 시간 복잡도는 O(n log S)이고, 추가 공간 복잡도는 O(1)입니다.