문제 설명

공장은 m개의 생산 라인을 운영하며, n개의 독립적인 작업을 병렬 처리해야 합니다. 시스템은 항상 처리 시간이 가장 짧은 작업부터 우선 배치합니다. 각 작업의 처리 시간이 주어졌을 때, 모든 작업이 완료되는 총 소요 시간을 구하세요.

작업 수가 라인 수를 초과하면, 처음에 처리 시간이 짧은 m개의 작업이 라인에 할당되고, 이후 한 라인이 작업을 완료할 때마다 남은 작업 중 가장 짧은 것을 차례로 배정합니다.

입력 형식

• 첫째 줄: m (라인 수), n (작업 수)
• 둘째 줄: 각 작업의 처리 시간 t1, t2, ..., tn

출력 형식

모든 작업이 완료되는 총 시간 출력

예제

입력:
3 5
8 4 3 2 10

출력:
13

해결 전략: 그리디 + 최소 힙 활용

이 문제는 자원 할당 최적화의 대표적인 사례입니다. 핵심 아이디어는 다음과 같습니다:

• 작업은 반드시 처리 시간이 짧은 순서로 처리되어야 하며,
• 비어 있는 라인은 언제나 가장 짧은 남은 작업을 받아야 합니다.

따라서 알고리즘은 다음과 같이 구성됩니다:

1. 작업 목록을 오름차순 정렬하여 짧은 작업부터 처리.
2. 최소 힙(우선순위 큐)을 사용해 각 라인의 다음 완료 예정 시간을 관리.
3. 처음 m개의 작업을 힙에 삽입.
4. 남은 작업들에 대해, 힙에서 가장 빨리 끝나는 라인을 꺼내고, 그 라인에 현재 작업을 할당.
5. 모든 작업 배치 후, 힙 내부의 최대값이 전체 완료 시간입니다.

코드 구현

Java 버전

import java.util.PriorityQueue;
import java.util.Arrays;
import java.util.Scanner;

public class TaskScheduler {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();
        int n = sc.nextInt();
        
        int[] durations = new int[n];
        for (int i = 0; i < n; i++) {
            durations[i] = sc.nextInt();
        }
        
        Arrays.sort(durations);
        
        if (n <= m) {
            System.out.println(durations[n - 1]);
            return;
        }
        
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        
        for (int i = 0; i < m; i++) {
            heap.offer(durations[i]);
        }
        
        for (int i = m; i < n; i++) {
            int earliest = heap.poll();
            heap.offer(earliest + durations[i]);
        }
        
        int maxCompletionTime = 0;
        for (int time : heap) {
            if (time > maxCompletionTime) {
                maxCompletionTime = time;
            }
        }
        
        System.out.println(maxCompletionTime);
        sc.close();
    }
}

Go 버전

package main

import (
	"container/heap"
	"fmt"
	"sort"
)

type MinHeap []int

func (h MinHeap) Len() int           { return len(h) }
func (h MinHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h MinHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *MinHeap) Push(x interface{}) {
	*h = append(*h, x.(int))
}

func (h *MinHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}

func solve() {
	var m, n int
	fmt.Scan(&m, &n)
	
	tasks := make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Scan(&tasks[i])
	}
	
	sort.Ints(tasks)
	
	if n <= m {
		fmt.Println(tasks[n-1])
		return
	}
	
	h := &MinHeap{}
	heap.Init(h)
	
	for i := 0; i < m; i++ {
		heap.Push(h, tasks[i])
	}
	
	for i := m; i < n; i++ {
		earliest := heap.Pop(h).(int)
		heap.Push(h, earliest + tasks[i])
	}
	
	maxTime := 0
	for _, t := range *h {
		if t > maxTime {
			maxTime = t
		}
	}
	
	fmt.Println(maxTime)
}

func main() {
	solve()
}

핵심 원리 해설

• 작업 정렬 필수성: 짧은 작업부터 처리하라는 조건을 만족하기 위해 반드시 정렬이 필요합니다.
• 최소 힙의 역할: 라인의 다음 완료 시간 중 가장 작은 값을 빠르게 찾기 위해 사용됩니다.
• 결과 값의 특성: 전체 완료 시간은 가장 늦게 끝나는 라인의 시간이며, 이는 힙 내부의 최댓값입니다.
• 경계 처리: 작업 수가 라인 수 이하일 경우, 최대 처리 시간만 반환하면 됩니다.