Book Allocation Problem

Q: 책 할당 문제는 배열을 나누어 가장 큰 합을 구하는 문제와 같은가요?

맞습니다. 둘 다 배열을 고정된 개수의 비어 있지 않은 연속 블록으로 나누고 가장 큰 블록 합을 최소화하며, 같은 이진 탐색과 같은 그리디 검사로 둘 다 해결할 수 있습니다. 책의 버전에는 -1 인 경우가 추가됩니다.

Q: 책 할당 문제의 시간 복잡도는 얼마인가요?

시간은 O(n log S) 이고 추가 공간은 O(1) 이며, 여기서 n 은 책의 수이고 S 는 전체 페이지 수입니다. 시도하는 각 한계값마다 책을 한 번씩 훑어야 하며, 탐색에서는 약 log2 S 개의 한계값을 시도합니다. 5 × 10^8 페이지짜리 책장에서는 29개입니다.

Q: 책을 할당하는 것이 불가능한 경우는 언제인가요?

모든 학생에게 최소 한 권의 책이 필요하므로 학생 수가 책 수보다 많을 때만 해당됩니다. 책이 충분하다면 두 권 이상의 책이 있는 어떤 묶음이든 마지막 책을 책이 없는 학생에게 줄 수 있으며, 모든 학생이 책을 한 권씩 가질 때까지 계속하면 됩니다.

보통이진 탐색 그리디

+10

선반에는 책들이 정해진 순서로 놓여 있고, pages[i]는 i번째 책의 페이지 수입니다. 책을 students명의 학생에게 나누어 주세요. 각 학생은 이웃한 책을 끊김 없이 이어지는 한 구간으로 받으며, 각 학생은 최소 한 권씩 받고, 모든 책은 정확히 한 명의 학생에게 배정됩니다. 학생의 할당량은 그 학생이 받은 책의 총 페이지 수입니다.

가장 무거운 할당량의 가능한 최솟값을 반환하세요. 학생 수가 책 수보다 많으면 -1을 반환하세요.

함수

allocateBooks(pages: integer-array, students: integer) → integer

pagesinteger-array: 책장에 놓인 순서대로 각 책의 페이지 수
studentsinteger: 책을 함께 나누는 학생 수
반환값integer: 가능한 가장 작은 최대 적재량, 또는 학생 수가 책 수보다 많으면 -1

제약 조건

1 ≤ pages.length ≤ 5000
1 ≤ pages[i] ≤ 10⁵
1 ≤ students ≤ 10⁴
students > pages.length일 때 -1을 반환합니다.

예제

입력: pages = [25, 40, 15, 30, 50]students = 3
출력: 65
설명: [25, 40], [15, 30], [50]을 나눠 주면 각 묶음의 합은 65, 45, 50입니다. 한도가 64이면 실패합니다. 나눠 주면 [25], [40, 15], [30], [50]이 되어 학생이 네 명이 됩니다.

입력: pages = [10, 20]students = 3
출력: -1
설명: 책 두 권으로는 학생 세 명에게 한 권씩 나눠 줄 수 없으므로 답은 -1입니다.

후속 질문

평균 몫을 올림한 값에 가장 두꺼운 책의 두께를 더하면 항상 유효한 상한이 됨을 증명하세요. 얇은 책들로 이루어진 선반에서는 이 상한으로 검사 횟수를 얼마나 줄일 수 있나요?

힌트

하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.

3개 중 0개 열림

풀이

책을 나누는 방법은 너무 많지만, 페이지 제한 하나를 시험하는 것은 간단합니다. 책장 순서대로 책을 나눠 주다가 책 한 권을 더 주면 제한을 넘게 될 때 다음 학생에게 넘기고, 학생 수를 세면 됩니다. 제한이 높아져도 필요한 학생 수는 늘어나지 않으므로, 조건을 만족하는 제한은 연속된 구간을 이루며 이 구간이 시작되는 지점을 이진 탐색으로 찾을 수 있습니다.

페이지 제한을 한 번에 한 페이지씩 늘리세요

정답이지만 가장 큰 테스트에서는 끝나지 않음

핵심 아이디어

L = max(pages)에서 시작하세요. 누군가는 가장 두꺼운 책을 맡게 되므로, 탐욕적으로 계산한 학생 수가 students에 맞을 때까지 L을 한 페이지씩 늘리세요. 그보다 낮은 모든 상한은 조건을 만족하지 못했으므로, 조건을 만족하는 첫 번째 값이 답입니다. 첫 번째 예에서는 50부터 64까지의 모든 상한에서 학생 4명이 필요하고, 65에서는 3명이 필요합니다. 총 16번 확인합니다.

답은 책장에 있는 책 전체를 한 학생에게 맡기는 경우일 수도 있습니다. 책 5000권이 있고 각 책이 10^5페이지라면, 약 5 × 10^8개의 상한을 확인해야 하며, 각각은 책 5000권을 한 번 훑는 과정입니다. 시간 열에서 A는 답이고 m은 가장 두꺼운 책입니다.

알고리즘

students > pages.length이면 -1을 반환합니다.
제한값 L에 대한 그리디 방식의 인원수를 작성합니다. 학생 한 명과 할당량 0으로 시작합니다. load + pages[i] > L이면 학생을 한 명 추가하고 할당량을 pages[i]로 설정합니다. 그렇지 않으면 책을 할당량에 더합니다.
L을 가장 두꺼운 책의 두께로 설정합니다.
L에 대한 인원수가 students보다 많으면 L에 1을 더합니다.
L을 반환합니다.

def studentsNeeded(pages, limit):
    count, load = 1, 0  # the first student starts with no pages
    for p in pages:
        if load + p > limit:
            count += 1  # this book opens the next student's block
            load = p
        else:
            load += p
    return count


def allocateBooks(pages, students):
    if students > len(pages):
        return -1  # someone would get no book
    limit = max(pages)  # the thickest book has to fit somewhere
    while studentsNeeded(pages, limit) > students:
        limit += 1
    return limit

페이지 제한에 대한 이진 검색

핵심 아이디어

탐욕적 방식에서 필요한 학생 수는 공유 방식 중 L 이하의 한도를 지키면서 사용할 수 있는 학생 수의 최솟값입니다. 다른 어떤 공유 방식과 학생별로 비교해도, 탐욕적 방식의 각 학생은 다음 책이 들어가지 않을 때에만 멈추므로 책장 위에서 적어도 그만큼 더 진행합니다. 학생 수가 실제 보유한 학생 수보다 적어도 괜찮습니다. 책을 두 권 가진 학생이 한 권을 책이 없는 학생에게 넘길 수 있고, 어느 학생의 부담도 늘어나지 않기 때문입니다.

따라서 L은 탐욕적 방식에 필요한 학생 수가 students 이하일 때에만 가능합니다. L에서 가능한 방식은 L+1에서도 가능하므로, 이진 탐색으로 가능한 최초의 한도를 찾을 수 있습니다.

탐색 범위의 시작값은 max(pages)와 평균 분배량인 total / students를 올림한 값 중 더 큰 값입니다. 가장 많은 부담은 이 두 값보다 작을 수 없기 때문입니다. 상한은 total입니다. 첫 번째 예시에서는 54부터 160까지이며, 탐색 과정에서 107, 80, 67, 60, 64, 66, 65를 시도합니다.

알고리즘

students > pages.length이면 -1을 반환합니다.
total을 모두 더하고 가장 두꺼운 책을 찾습니다. lo를 가장 두꺼운 책과 (total + students - 1) / students 중 큰 값으로 설정하고, hi = total로 설정합니다.
lo < hi인 동안 mid = lo + (hi - lo) / 2를 계산합니다.
mid에 대해 그리디 방식으로 개수를 셉니다. 그 값이 students 이하이면 hi = mid로 설정하고, 그렇지 않으면 lo = mid + 1로 설정합니다.
lo를 반환합니다.

def studentsNeeded(pages, limit):
    count, load = 1, 0  # the first student starts with no pages
    for p in pages:
        if load + p > limit:
            count += 1  # this book opens the next student's block
            load = p
        else:
            load += p
    return count


def allocateBooks(pages, students):
    if students > len(pages):
        return -1  # someone would get no book
    total = sum(pages)
    # no limit can be below the thickest book or below the average share
    lo = max(max(pages), (total + students - 1) // students)
    hi = total  # one student could carry the whole shelf
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if studentsNeeded(pages, mid) <= students:
            hi = mid  # mid is enough, so the answer is mid or lower
        else:
            lo = mid + 1  # mid needs too many students
    return lo

함정과 경계 사례

-1 검사를 건너뛰는 경우. [10, 20]과 학생 3명일 때, 제한값이 20이면 그리디 방식의 개수는 2이므로 탐색 결과는 20입니다.
범위를 평균 분배량만으로 시작하는 경우. [1, 9]와 학생 2명일 때 평균은 5이고, 이 경우 그리디 방식은 9페이지짜리 책을 혼자 배정하여 개수를 2로 계산하고 5를 반환합니다.
정확히 students인지 검사하는 경우. [5, 5, 5, 5, 5, 5]와 학생 4명일 때 정답은 10이며, 그리디 방식의 개수는 3입니다.
책을 정렬하는 경우. 학생 2명일 때 [10, 1, 1, 10]의 결과는 11이지만, [1, 1, 10, 10]으로 정렬하면 결과는 12입니다.

자주 묻는 질문3

책 할당 문제는 배열을 나누어 가장 큰 합을 구하는 문제와 같은가요?

맞습니다. 둘 다 배열을 고정된 개수의 비어 있지 않은 연속 블록으로 나누고 가장 큰 블록 합을 최소화하며, 같은 이진 탐색과 같은 그리디 검사로 둘 다 해결할 수 있습니다. 책의 버전에는 -1인 경우가 추가됩니다.

책 할당 문제의 시간 복잡도는 얼마인가요?

시간은 O(n log S)이고 추가 공간은 O(1)이며, 여기서 n은 책의 수이고 S는 전체 페이지 수입니다. 시도하는 각 한계값마다 책을 한 번씩 훑어야 하며, 탐색에서는 약 log2 S개의 한계값을 시도합니다. 5 × 10^8페이지짜리 책장에서는 29개입니다.

책을 할당하는 것이 불가능한 경우는 언제인가요?

모든 학생에게 최소 한 권의 책이 필요하므로 학생 수가 책 수보다 많을 때만 해당됩니다. 책이 충분하다면 두 권 이상의 책이 있는 어떤 묶음이든 마지막 책을 책이 없는 학생에게 줄 수 있으며, 모든 학생이 책을 한 권씩 가질 때까지 계속하면 됩니다.

def allocateBooks(pages, students):
    # 여기에 코드를 작성하세요

테스트 #1

테스트 #2

테스트 #3

인자들

pages = [25, 40, 15, 30, 50]
students = 3

예상 출력