[백준] 2343번 : 기타 레슨

🔗 문제 링크

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

✍️ 문제 풀이

해당 문제는 이진 탐색 중에서 lowerBound를 이용했다. 가능한 블루레이 크기 중 최소 (== 가능한 크기 중 가장 처음)를 구해야하기 때문이다.

1) 각 강의들의 길이를 저장하는 벡터를 선언하고, 입력 받은 순서대로 각 강의 길이들을 벡터에 삽입한다. 삽입 할 때마다 sum에 강의 길이를 누적시켜 전체 강의 길이를 저장한다.

2) 전체 강의 길이(sum)를 블루레이 개수(m)으로 나눈 값을 반올림해 최선의 경우의 최소 블루레이 크기를 minBlu에 저장해둔다.

3) lowerBound() 함수를 실행해 가능한 최소 블루레이 크기를 반환해 출력한다.

• start = minBlu, end = sum으로 초기화 한다. (mid는 두 값의 합의 절반)
• 강의가 저장된 순서대로 탐색하면서 각 강의 길이를 tmpSum에 누적시킨다.
  • 만약 tmpSum이 mid보다 커지면
    • count를 1 증가 시킨다. (count == 사용한 블루레이 개수 저장)
    • 반복문 변수 i를 1 감소시켜 초과된 인덱스부터 다시 탐색하도록 한다.
    • 그 다음 수부터 누적 길이를 다시 구하기 위해 tmpSum을 0으로 초기화한다.
      ❗여기서 꼭 해주어야 하는 처리가 있는데, count가 제한 블루레이 개수(m)을 넘어서는 순간 break하여 반복문을 빠져나가는 것이다. 만약 mid 값이 한 강의 길이보다 작다면 한 강의만 누적해도 tmpSum이 mid보다 커지기 때문에 한 자리에서 무한 루프가 발생하게 된다. 따라서 count가 제한 블루레이 개수를 넘어서는 순간 더 이상 실행하지 않아도 되기 때문에 반복문을 종료한다.
    • 그 결과 count가 m - 1보다 작거나 같으면 end를 mid의 자리로 옮겨준다.
    • m - 1보다 크다면 start를 mid + 1의 자리로 옮겨준다.
• 위 과정을 반복하면서 start와 end 위치를 옮기다가 end가 start보다 크지 않게 되는 순간(!(end > start))의 end 값을 반환해 출력한다.

🖥️ 풀이 코드

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
using namespace std;

vector<int> arr;
int input;
int sum = 0;        // 전체 강의 길이
int minBlu = 0;     // 전체 강의 길이 / 블루레이 개수 (최선의 경우의 최소 블루레이 크기)

int lowerBound(int n, int m)
{
    int start = minBlu, end = sum, mid;   // start : 최선의 경우 최소 블루레이 크기 

    while (end > start)
    {
        mid = (start + end) / 2;
        int tmpSum = 0;
        int count = 0;
        for (int i = 0; i < n; i++)
        {
            tmpSum += arr[i];
            if (tmpSum > mid)
            {
                count++;
                i -= 1;
                tmpSum = 0;
                if (count > m)  // 이거 안 해줘서 시간 초과 발생 ( ex. mid가 8이고 arr[i]가 9이면 tmpSum이 계속 mid를 초과하기 때문에 무한 루프 발생 -> count가 블루레이 개수 넘어서면 break )
                    break;      // 7 7
                                // 5 9 6 8 7 7 5
                                // 답: 9
            }
        }
        if (count <= m - 1)
            end = mid;
        else
            start = mid + 1;
    }
    return end;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(); cout.tie();

    int n;
    float m;
    cin >> n >> m;

    for (int i = 0; i < n; i++)
    {
        cin >> input;
        arr.push_back(input);
        sum += input;
    }
    minBlu = round(sum / m);
    cout << lowerBound(n, m);
}