C++로 풀어보는 최소 페이지 수 할당 문제

최소 페이지 수 할당(Minimum Number of Pages Allocation)은 코딩 테스트와 알고리즘 학습에서 자주 등장하는 대표적인 문제입니다. 이 글에서는 문제를 자세히 살펴보고, 이진 탐색(Binary Search)을 활용한 효율적인 해결 방법까지 단계별로 알아보겠습니다.

문제 정의

서로 다른 n권의 책이 있고, 각 책의 페이지 수가 주어집니다. 또한 이 책들을 나누어 받을 m명의 학생이 있습니다. 조건은 다음과 같습니다.

책들은 페이지 수 기준으로 오름차순 정렬되어 있습니다.
각 학생에게는 반드시 연속된 책들만 할당할 수 있습니다.
프로그램은 학생 한 명이 읽게 되는 최대 페이지 수를 구하되, 그 값이 가능한 한 최소가 되도록 해야 합니다.

예제를 통해 문제를 더 명확히 이해해 보겠습니다.

Input : books[] = {13, 43, 65, 87, 92}
m = 2
Output : 179

예제 상세 설명

이 예제에서는 두 명의 학생이 책을 읽습니다. 책을 나누는 방법은 다음과 같이 네 가지 경우가 가능합니다.

CASE 1 — [13], [43, 65, 87, 92]
학생들이 읽는 페이지 수는 13 / 287이며, 최대값은 287입니다.

CASE 2 — [13, 43], [65, 87, 92]
학생들이 읽는 페이지 수는 56 / 244이며, 최대값은 244입니다.

CASE 3 — [13, 43, 65], [87, 92]
학생들이 읽는 페이지 수는 121 / 179이며, 최대값은 179입니다.

CASE 4 — [13, 43, 65, 87], [92]
학생들이 읽는 페이지 수는 208 / 92이며, 최대값은 208입니다.

네 가지 경우 중 학생 한 명이 읽는 최대 페이지 수가 가장 작은 경우는 CASE 3의 179입니다. 따라서 정답은 179가 됩니다.

해결 접근 방법: 이진 탐색

이 문제를 효율적으로 해결하는 방법은 이진 탐색 알고리즘을 사용하는 것입니다. 접근 과정은 다음과 같습니다.

탐색 범위의 하한(minimum)을 0으로, 상한(maximum)을 모든 책의 페이지 수 합계로 초기화합니다.
두 값의 중간값(mid)을 임시 결과로 설정하고, 알고리즘이 진행됨에 따라 이 값을 조정합니다.
mid 값을 기준으로 해당 값이 유효한 해가 될 수 있는지 검사합니다. 만약 mid가 해가 될 가능성이 있다면 탐색 범위를 하반부(minimum ~ mid)로 좁히고, 그렇지 않다면 상반부(mid ~ maximum)를 탐색합니다.

이 방식으로 문제를 해결할 수 있지만, 학생 수가 많아질수록 알고리즘의 신뢰성이 떨어질 수 있다는 점에 유의해야 합니다.

C++ 구현 예제

#include<bits/stdc++.h>
using namespace std;
bool isPossible(int arr[], int n, int m, int curr_min) ;
int min_pages(int arr[], int n, int m) ;
int main(){
    int n = 5;
    int books[] = {13, 43, 65, 87, 92};
    cout<<"The number of page in books are :\n";
    for(int i = 0 ; i< n; i++){
        cout<<books[i]<<"\t";
    }
    int m = 2;
    cout<<"\nMinimum number of pages = "<<min_pages(books, n, m)<<endl;
    return 0;
}
bool isPossible(int arr[], int n, int m, int curr_min){
    int studentsRequired = 1;
    int curr_sum = 0;
    for (int i = 0; i < n; i++){
        if (arr[i] > curr_min)
            return false;
        if (curr_sum + arr[i] > curr_min){
            studentsRequired++;
            curr_sum = arr[i];
            if (studentsRequired > m)
                return false;
        }
        else
            curr_sum += arr[i];
    }
    return true;
}
int min_pages(int arr[], int n, int m){
    long long sum = 0;
    if (n < m)
        return -1;
    for (int i = 0; i < n; i++)
        sum += arr[i];
    int minimum = 0, maximum = sum;
    int result = INT_MAX;
    while (minimum <= maximum){
        int mid = (minimum + maximum) / 2;
        if (isPossible(arr, n, m, mid)){
            result = min(result, mid);
            maximum = mid - 1;
        }
        else
            minimum = mid + 1;
    }
    return result;
}

코드 동작 원리

isPossible() 함수는 현재 시도하는 최소 페이지 수(curr_min)로 m명의 학생에게 책을 나누어 줄 수 있는지 판단합니다. 특정 책의 페이지 수가 curr_min보다 크거나, 필요한 학생 수가 m명을 초과하면 불가능하다고 반환합니다.

min_pages() 함수는 실제 이진 탐색을 수행합니다. 책의 수가 학생 수보다 적으면 나누어 줄 수 없으므로 -1을 반환하고, 그렇지 않으면 탐색 범위 내에서 가능한 최솟값을 찾아 반환합니다.

실행 결과

The number of page in books are :
13 43 65 87 92
Minimum number of pages = 179