서로 다른 소요 시간을 가진 여러 작업(job)의 배열이 있고, 이를 수행할 k명의 담당자가 있다고 가정해 봅시다. 또한 각 담당자가 작업 한 단위를 처리하는 데 걸리는 시간 t도 주어집니다. 우리는 다음과 같은 제약 조건 하에 모든 작업을 완료하는 데 필요한 최소 시간을 구해야 합니다.
한 명의 담당자에게는 연속된 작업만 배정할 수 있습니다.
두 명의 담당자가 하나의 작업을 나누어 수행하거나 공유할 수 없습니다.
예를 들어, 입력이 k = 4, t = 5, job = {12, 6, 9, 15, 5, 9}라면 출력은 75가 됩니다. 이는 [12], [6, 9], [15], [5, 9]와 같이 작업을 네 명의 담당자에게 배정했을 때 얻을 수 있는 총 소요 시간입니다.
접근 방법: 이진 탐색 활용
이 문제는 이진 탐색(Binary Search)을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 "주어진 시간 안에 k명의 담당자로 모든 작업을 완료할 수 있는가?"를 판단하는 유효성 검사 함수를 만들고, 가능한 시간 범위(0부터 모든 작업 시간의 합까지)에서 이진 탐색을 수행하는 것입니다. 어떤 시간 X로 작업 완료가 가능하다면 X보다 큰 시간으로도 항상 가능하기 때문에, 탐색 범위를 절반씩 줄여나갈 수 있습니다.
1. 유효성 검사 함수 (is_valid)
is_valid() 함수는 특정 시간(time) 내에 K명의 담당자로 모든 작업을 완료할 수 있는지 확인합니다. 동작 과정은 다음과 같습니다.
n := job 배열의 크기
count := 1 (필요한 담당자 수), curr_time := 0 (현재 담당자의 누적 작업 시간), i := 0
i < n인 동안 반복:
curr_time + job[i] > time이면 → 새로운 담당자가 필요하므로 curr_time := 0, count := count + 1
그렇지 않으면 → 현재 담당자에게 작업을 추가: curr_time := curr_time + job[i], i := i + 1
count <= K이면 true 반환
2. 메인 함수 (get_minimum_time)
n := job 배열의 크기
end := 모든 작업 시간의 합, begin := 0
res := end (초기 결과값)
job_max := job 배열의 최댓값 (가장 오래 걸리는 단일 작업 — 이 값보다 작은 시간으로는 해당 작업을 완료할 수 없음)
begin <= end인 동안 이진 탐색 반복:
mid := ((begin + end) / 2)의 정수 부분
mid >= job_max이고 is_valid(mid, K, job)가 참이면 → res := min(res, mid), end := mid - 1 (더 작은 시간 탐색)
그렇지 않으면 → begin := mid + 1 (더 큰 시간 탐색)
res * T 반환 (작업 단위당 실제 소요 시간 T를 곱해 최종 결과 계산)
구현 예시
아래 파이썬 코드를 통해 더 잘 이해해 봅시다.
def is_valid(time, K, job):
n = len(job)
count = 1
curr_time = 0
i = 0
while i < n:
if curr_time + job[i] > time:
curr_time = 0
count += 1
else:
curr_time += job[i]
i += 1
return count <= K
def get_minimum_time(K, T, job):
n = len(job)
end = 0
begin = 0
for i in range(n):
end += job[i]
res = end
job_max = max(job)
while begin <= end:
mid = int((begin + end) / 2)
if mid >= job_max and is_valid(mid, K, job):
res = min(res, mid)
end = mid - 1
else:
begin = mid + 1
return res * T
job = [12, 6, 9, 15, 5, 9]
k = 4
T = 5
print(get_minimum_time(k, T, job))입력
4, 5, [12, 6, 9, 15, 5, 9]
출력
75
복잡도 분석
시간 복잡도: O(n × log S) — S는 모든 작업 시간의 합입니다. 매번 이진 탐색 범위가 절반으로 줄어들고, 각 단계마다 O(n)의 유효성 검사를 수행합니다.
공간 복잡도: O(1) — 추가적인 배열 없이 상수 개의 변수만 사용합니다.
이처럼 이진 탐색과 그리디한 유효성 검사를 결합하면, 모든 경우의 수를 확인하는 비효율적인 방법 대신 빠르게 최소 완료 시간을 구할 수 있습니다.