문제 개요

길이가 각각 $ L_i $인 $ n $개의 나무 막대가 연속적으로 연결되어 있습니다. 이 중에서 최대 $ m $개의 접합부를 자를 수 있으며, 자른 후 만들어진 조각들 중 가장 긴 조각의 길이가 최소가 되도록 해야 합니다. 또한, 그러한 조합의 경우의 수를 구하고 결과를 $ 10007 $로 나눈 나머지를 출력해야 합니다.

해법 접근

이 문제는 두 가지 부분으로 나뉩니다: 1. 최대 조각 길이의 최솟값을 찾기 위한 이분 탐색 2. 그 값에 대해 가능한 자르는 방법의 수를 동적 프로그래밍으로 계산

이분 탐색을 통한 최소 길이 결정

최소화해야 할 값은 최대 조각 길이이므로, 이 값을 기준으로 이분 탐색을 수행합니다. 가능한 범위는 $ [\max(L_i), \sum L_i] $입니다. 각각의 후보 길이 $ mid $에 대해, 해당 길이로 전체 막대를 분할할 수 있는지 여부를 확인하는 함수를 작성합니다.

bool check(ll mid) {
    ll current = 0;
    int cuts = 0;
    for (int i = 1; i <= n; ++i) {
        if (current + a[i] <= mid)
            current += a[i];
        else {
            current = a[i];
            cuts++;
            if (cuts > m) return false;
        }
    }
    return true;
}

동적 프로그래밍으로 경우의 수 계산

이제 최소 길이 $ len $이 결정되었으므로, 이를 기준으로 가능한 분할 방법의 수를 세어야 합니다. 전형적인 $ O(n^2m) $ DP는 시간 초과가 발생하므로, 효율적인 최적화가 필요합니다.

다음과 같은 아이디어를 사용합니다:

• $ f[i][j] $: 첫 번째부터 $ j $번째 막대까지 $ i $조각으로 나누는 경우의 수
• 하지만 메모리와 시간 복잡도를 줄이기 위해, 단일 배열과 전후 고정된 인덱스를 이용한 슬라이딩 윈도우 방식을 적용
• 각 위치 $ i $에서, $ sum[i] - sum[j] \leq len $을 만족하는 최대 $ j $를 미리 계산하여 $ rem[i] $에 저장
• 전위 합 배열 $ S $를 사용하여 구간 합을 빠르게 계산

int dp() {
    // rem[i]: sum[i] - sum[rem[i]] ≤ len 를 만족하는 최소 인덱스
    int k = 0;
    for (int i = 1; i <= n; ++i) {
        while (k < i && sum[i] - sum[k] <= len)
            ++k;
        rem[i] = k - 1;
    }

    // 초기 상태: 하나의 조각으로 만들 수 있는 경우
    int res = (sum[n] <= len);
    for (int i = 1; i <= n; ++i) {
        f[i] = (sum[i] <= len);
        S[i] = (S[i-1] + f[i]) % mod;
    }

    // m+1번 분할까지 진행 (최대 m번 자름 → 총 조각 수는 m+1)
    for (int group = 2; group <= m + 1; ++group) {
        for (int i = 1; i <= n; ++i) {
            f[i] = S[i-1];  // 이전까지의 모든 경우
            if (rem[i] >= 0)
                f[i] = (f[i] - S[rem[i]] + mod) % mod;
        }
        // 새로운 전위 합 갱신
        for (int i = 1; i <= n; ++i)
            S[i] = (S[i-1] + f[i]) % mod;
        res = (res + f[n]) % mod;
    }
    return res;
}

결과 출력

이분 탐색을 통해 최소 최대 길이 $ len $을 찾고, $ dp() $ 함수로 경우의 수를 계산하여 출력합니다.