항해99 백준 2343번 // 블루레이 강의

https://www.acmicpc.net/problem/2343

 

 

강토는 강의의 동영상을 블루레이에 저장하려고 합니다. 총 NNN개의 강의가 있으며, MMM개의 블루레이를 사용하여 강의를 저장해야 합니다. 이때 다음 조건을 만족해야 합니다:
블루레이 하나에 포함된 강의들은 순서가 바뀌면 안 됩니다.각 강의의 길이는 주어지며, 하나의 블루레이에 녹화되는 강의들의 총 길이가 블루레이의 용량을 초과하면 안 됩니다.MMM개의 블루레이를 모두 사용하는 상황에서, 블루레이의 크기(용량)를 최소화해야 합니다

그리디 알고리즘과 이진탐색

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;

// 블루레이 크기로 강의들을 나눌 수 있는지 확인하는 그리디 알고리즘을 이용한 함수
bool isPossible(const vector<int>& lectures, int n, int m, int maxSize) 
{
    int count = 1; // 사용한 블루레이 개수
    int currentSum = 0; // 현재 블루레이에 들어간 강의 길이 합

    for (int lecture : lectures) 
    {
        if (currentSum + lecture > maxSize) 
        {
            count++; // 새로운 블루레이 사용
            currentSum = lecture; // 현재 블루레이에 강의 추가
            if (count > m) 
            {
                return false; // 블루레이 개수 초과
            }
        } 
        else 
        {
            currentSum += lecture;
        }
    }

    return true;
}

// 가능한 최소 블루레이 크기를 찾는 이분탐색 수행하는 함수
int findMinimumBluraySize(const vector<int>& lectures, int n, int m) 
{
    int left = *max_element(lectures.begin(), lectures.end()); // 가장 긴 강의의 길이
    int right = accumulate(lectures.begin(), lectures.end(), 0); // 모든 강의 길이 합
    int result = right;

    while (left <= right) 
    {
        int mid = (left + right) / 2; // 중간 크기
        if (isPossible(lectures, n, m, mid)) 
        {
            result = mid; // 가능한 경우 결과 저장
            right = mid - 1; // 더 작은 크기 탐색
        } 
        else 
        {
            left = mid + 1; // 더 큰 크기 탐색
        }
    }

    return result;
}

int main() 
{
    int n, m; //1<=m<=n=100,000 
    cin >> n >> m;

    vector<int> lectures(n);
    for (int i = 0; i < n; i++) 
    {
        cin >> lectures[i];
    }

    cout << findMinimumBluraySize(lectures, n, m) << endl; // 결과 출력

    return 0;
}

 

9개의 lectures, 3개의 블루레이로 나누기

1,2,3,4,5,6,7,8,9

1. 초기

 left =9; right = 45; mid=27;

    isPossible(lectures, 9,3, 27)

     27보다 작은 면 1,2,3,4,5,6=21

     21+7은 28로 count++해주고 currentLecture = 7

     7+8+9=24 로 가능
     return 27(result=27, right=27-1)

   isPossible( lectures, 9,3, 26)

     left =9; right = 26; mid=17;

     1,2,3,4,5 count1

      6 7 8= 21 count2

      9 = count 3 -> return 17

  isPossible(lectures, 9,3,right = 16)

   left =9, right =16, mid =12;

   1,2,3,4

    5,6,

    7,8

    9 

   count=4
   left 13