문제 설명
jobs라는 배열이 있다고 가정해 보겠습니다. 여기서 jobs[i]는 i번째 작업을 완료하는 데 필요한 시간을 의미합니다. 또 하나의 값 k가 주어지는데, 이는 작업을 배정받을 수 있는 작업자(worker)의 수입니다. 각 작업은 반드시 정확히 한 명의 작업자에게 배정되어야 하며, 한 작업자의 작업 시간이란 그 작업자에게 배정된 모든 작업을 완료하는 데 걸리는 총 시간을 뜻합니다. 우리의 목표는 어떤 배정 방식이든 최대 작업 시간이 최소가 되도록 만드는 것입니다.
예를 들어 입력이 jobs = [2,1,3,8,5], k = 2라고 한다면 출력은 10이 됩니다. 작업을 다음과 같이 배정할 수 있기 때문입니다.
작업자 1: 2 + 5 + 3 = 10
작업자 2: 1 + 8 = 9
두 작업자 중 더 오래 걸리는 시간은 10이므로, 이 배정에서 최대 작업 시간은 10입니다.
해결 접근 방법
이 문제는 백트래킹(backtracking) 기법으로 해결할 수 있습니다. 각 작업을 k명의 작업자 중 한 명에게 순서대로 배정해 보면서, 모든 작업이 배정된 시점의 최대 작업 시간을 계산하고 그중 최솟값을 찾습니다. 작업 시간이 긴 작업부터 먼저 배정하면 탐색 범위를 줄여 효율을 높일 수 있습니다. 구체적인 단계는 다음과 같습니다.
jobs 리스트를 내림차순으로 정렬합니다.
assign := 처음 k개의 작업으로 구성된 리스트
jobs := 나머지 작업들의 리스트
dp() 함수를 정의합니다. 이 함수는 i와 assign을 매개변수로 받습니다.
i가 jobs의 크기와 같다면, assign의 최댓값을 반환합니다.
ans := 무한대(infinity)
x를 0부터 k-1까지 반복하면서 다음을 수행합니다.
assign := assign의 복사본(새 리스트)
assign[x] := assign[x] + jobs[i]
ans := ans와 dp(i+1, assign) 중 최솟값
assign[x] := assign[x] - jobs[i]
ans를 반환합니다.
메인 메서드에서는 dp(0, assign)을 반환합니다.
예제 코드
더 나은 이해를 위해 다음 구현을 살펴보겠습니다.
def solve(jobs, k):
jobs.sort(reverse=True)
assign = tuple(jobs[:k])
jobs = jobs[k:]
def dp(i, assign):
if i == len(jobs):
return max(assign)
ans = float('inf')
for x in range(k):
assign = list(assign)
assign[x] += jobs[i]
ans = min(ans, dp(i+1, tuple(assign)))
assign[x] -= jobs[i]
return ans
return dp(0, assign)
jobs = [2,1,3,8,5]
k = 2
print(solve(jobs, k))
입력
[2,1,3,8,5], 2
출력
10