BOJ 2343 - 기타 레슨 링크
(2023.09.06 기준 S1)

문제

N개의 기타 강의의 길이가 주어진다. 이를 순서가 바뀌지 않게 블루레이에 녹화해야 하는데, 최대 블루레이의 개수가 M개로 정해져 있다. 이때, 블루레이의 크기 중 최솟값 출력

알고리즘

이분 탐색

풀이

블루레이의 크기가 작아질수록 블루레이의 개수는 늘어난다. 강의를 담을 수 있는 폭이 좁아지니 개수는 당연히 늘어날 수 밖에 없다.

이는 단조감소 함수 (f(블루레이 크기) = 블루레이 개수)이므로 이분 탐색을 사용 가능하다.
블루레이 크기를 조절하면서 기타 강의를 앞에서부터 최대한 담은 블루레이의 개수가 M개 이하인지 확인하면 된다.

코드

• C++

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int N, M; cin >> N >> M;
    int A[N]; for (int i = 0; i < N; i++) cin >> A[i];

    // 블루레이의 크기를 이분 탐색으로 조절하면서 최솟값을 찾자.
    int st = A[0]; for (int i = 1; i < N; i++) st = max(st, A[i]);// 최소는 기타 강의 중 최댓값
    int en = st * N; // 최대 강의의 길이의 합은 max(A) × N
    while (st < en){
        int mid = (st + en) >> 1;

        // 앞에서부터 mid 분을 넘지 않게끔 기타 강의를 최대한 담아서
        // 블루레이가 M개 이하가 되는지 확인
        int n = 1, l = 0; // 총 블루레이의 개수, 현재 블루레이의 크기
        for (auto a: A){
            if (l + a <= mid) l += a;
            else{
                n++;
                l = a;
            }
        }
    
        // 블루레이가 M개 이하가 되었다면 현재 크기는 가능한 크기
        if (n <= M) en = mid;
        else st = mid + 1;
    }

    cout << st;
}

• Python

import sys; input = sys.stdin.readline

N, M = map(int, input().split())
A = list(map(int, input().split()))

# 블루레이의 크기를 이분 탐색으로 조절하면서 최솟값을 찾자.
st = max(A) # 최소는 기타 강의 중 최댓값
en = st * N # 최대 강의의 길이의 합은 max(A) × N
while st < en:
    mid = (st + en) >> 1

    # 앞에서부터 mid 분을 넘지 않게끔 기타 강의를 최대한 담아서
    # 블루레이가 M개 이하가 되는지 확인
    n = 1; l = 0 # 총 블루레이의 개수, 현재 블루레이의 크기
    for a in A:
        if l + a <= mid:
            l += a
        else:
            n += 1
            l = a

    # 블루레이가 M개 이하가 되었다면 현재 크기는 가능한 크기
    if n <= M:
        en = mid
    else:
        st = mid + 1

print(st)