백준 2343번 [기타 레슨](C++) -yes6686- 티스토리

백준 문제 풀이: 2343 [기타 레슨]

---

문제 링크: https://www.acmicpc.net/problem/2343

문제 설명:

길이가 n인 강의 목록이 주어졌을 때, m개의 블루레이에 강의를 나누어 저장하려고 합니다. 이때, 블루레이의 크기가 최소가 되도록 해야 합니다. 블루레이의 크기는 각 블루레이에 들어가는 강의 길이 중 최댓값으로 결정됩니다.

즉, 최소한의 블루레이 크기를 이분 탐색을 사용하여 구하는 문제입니다.

---

문제 해결 코드

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

int arr[100001];

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

    int n, m;
    cin >> n >> m;

    int sum = 0;
    int maxV = 0;

    // 강의 길이 입력 및 총합 계산
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
        sum += arr[i];
        maxV = max(maxV, arr[i]);
    }

    int left = maxV; // 블루레이 크기의 최소값 (가장 긴 강의)
    int right = sum; // 블루레이 크기의 최대값 (모든 강의를 한 개의 블루레이에 담을 경우)
    int ans = right;

    // 이분 탐색 수행
    while (left <= right) {
        int mid = (left + right) / 2; // 블루레이 크기 후보
        int cnt = 1; // 필요한 블루레이 개수
        int tempSum = 0; // 현재 블루레이에 담긴 강의 길이 합

        for (int i = 0; i < n; i++) {
            if (tempSum + arr[i] > mid) { // 현재 블루레이에 더 담을 수 없을 경우
                cnt++;
                tempSum = 0;
            }
            tempSum += arr[i];
        }

        // 블루레이 개수가 m 이하라면 더 작은 크기를 시도
        if (cnt <= m) {
            ans = mid;
            right = mid - 1;
        } else { // 블루레이 개수가 초과하면 크기를 늘림
            left = mid + 1;
        }
    }

    // 최소 블루레이 크기 출력
    cout << ans << '\n';

    return 0;
}

예제 입력:

9 3
1 2 3 4 5 6 7 8 9

예제 출력:

17

---

코드 설명

• 핵심 알고리즘: 이분 탐색을 사용하여 블루레이의 최소 크기를 찾아 최적의 배치를 결정합니다.
• 구현 세부사항:
  • 블루레이의 최소 크기는 가장 긴 강의의 길이 이상이어야 합니다.
  • 블루레이의 최대 크기는 모든 강의를 하나의 블루레이에 저장하는 경우입니다.
  • 이분 탐색을 통해 적절한 블루레이 크기를 찾고, 해당 크기로 강의를 배치할 수 있는지 확인합니다.
  • 배치할 수 있는 경우 크기를 줄이고, 그렇지 않으면 크기를 늘려 탐색합니다.
• 시간 복잡도: O(n log sum), 여기서 sum은 강의 길이의 총합

---

결과

입력된 강의 목록과 블루레이 개수를 고려하여 최적의 블루레이 크기를 정확히 계산합니다. 이분 탐색을 활용한 범위 탐색 문제를 연습하기에 적합한 문제입니다. 추가적인 질문이나 개선 사항이 있다면 댓글로 알려주세요!