[PAST 알고리즘 시리즈] Part 1 보충 — 棒の出荷 문제 풀이

목차

Step	주제	핵심 질문
0	문제 이해하기	무엇을 구하는 문제인가?
1	완전 탐색의 한계	직접 풀면 왜 시간 초과인가?
2	판정 문제로 변환하기	어떤 질문으로 바꿀 수 있는가?
3	절단 범위 분석 — 누적합과 [l, r]	다음 절단 위치를 어떻게 구하는가?
4	판정 함수 v1 — O(N²) boolean 배열	가장 단순한 구현은?
5	판정 함수 v2 — O(N²) 투 포인터 최적화	l, r의 단조성을 어떻게 활용하는가?
6	판정 함수 v3 — O(N) いもす法	구간 갱신을 O(1)로 만드는 방법은?
7	이분 탐색으로 최적값 찾기	전체를 어떻게 조합하는가?
8	계산량 분석 & 정리	시간 안에 통과하는가?

Step 0 — 문제 이해하기

문제 요약

긴 막대를 적절히 잘라서 출하합니다:

• 좌우로 길게 뻗은 막대에 N−1개의 절단 위치가 있음
• 모든 절단 위치에서 자르면, 왼쪽부터 길이 $A_1, A_2, A_3, \ldots, A_N$인 N개의 막대로 나뉨
• N−1개의 절단 위치 중 일부(0개~전부)를 선택하여 절단
• 절단 후 모든 막대의 길이가 L 이하가 되도록 자름
• 막대 길이의 편차를 줄이기 위해, 가장 짧은 막대의 길이를 최대화
• 그 최대값을 출력하라

제약 조건

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq L \leq 10^{15}$
• $1 \leq A_i \leq \min(10^9, L)$
• 모든 값은 정수

입출력 예시

입력:

5 10
3 4 1 2 4

출력:

7

왼쪽에서 2번째 절단 위치만 선택하면, 두 막대의 길이는 각각 $3 + 4 = 7$과 $1 + 2 + 4 = 7$이 됩니다. 가장 짧은 막대의 길이는 7이며, 이것이 최대입니다.

Step 1 — 완전 탐색의 한계

가장 단순한 접근: 가능한 모든 절단 조합을 시도하고, 각 조합에서 가장 짧은 막대의 길이를 계산하여 최댓값을 구합니다.

조합 수 계산

N-1개의 절단 위치에 각각에 대해 "자르다/안 자른다" 2가지 선택이 있으므로:

$\text{전체 조합 수} = 2^{N-1}$

$N = 2 \times 10^5$일 때, $2^{199999}$는 천문학적 수치입니다.

각 조합에 대해 절단 후 막대 길이가 L 이하인지 확인하는 데 O(N)이 필요하므로, 전체 계산량은 $O(N \times 2^N)$입니다. 실행 시간 제한 내에 처리하는 것은 절대 불가능합니다.

Step 2 — 판정 문제로 변환하기

직접 최대값을 구하기 어려우니, 질문의 형태를 바꿔봅시다.

핵심 아이디어

원래 문제:

이를 다음과 같은 판정 문제(Yes/No 질문)로 바꿉니다:

이 판정 문제를 빠르게 풀 수 있다면, $X$의 값을 조절하여 최적의 $X$(= 최단 막대 길이의 최대값)를 찾을 수 있습니다.

단조성 확인

이 판정 문제의 답은 $X$의 값에 대해 단조적입니다:

X = 0        → ✅ (절단하지 않아도 길이 ≥ 0)
X = 1        → ✅ 
X = 5        → ✅ 
X = 7        → ✅  ← 여기가 최대값!
X = 8        → ❌ 
X = 10       → ❌
X = 100      → ❌

가능한 구간(✅)와 불가능한 구간(❌)의 경계가 정확히 하나만 존재 → 이분 탐색으로 경계를 찾을 수 있음!

Step 3 — 절단 범위 분석: 누적합과 [l, r] 구간

판정 문제를 풀기 위해, "절단 위치 i에서 절단한 뒤, 다음에 절단할 수 있는 위치는 어디인가?"를 분석합니다.

모델링

N-1개의 절단 위치에 왼쪽부터 1번, 2번, ..., N-1번으로 번호를 매깁니다. 추가로:

• 0번째 절단 위치 = 막대의 왼쪽 끝 (반드시 절단)
• N번째 절단 위치 = 막대의 오른쪽 끝 (반드시 절단)

누적합 배열

$S_0 = 0,\quad S_i = A_1 + A_2 + \cdots + A_i$

로 정의하면, 절단 위치 i에서 절단 위치 j까지의 막대 길이는 $S_j - S_i$입니다.

절단 가능 범위 [l, r]

절단 위치 i에서 절단했을 때, 다음으로 절단할 위치 j는 다음 두 조건을 동시에 만족해야 합니다:

1. 길이 X 이상: $S_j - S_i \geq X$ → 너무 가까이에서 자르면 짧은 막대가 생김
2. 길이 L 이하: $S_j - S_i \leq L$ → 너무 멀리에서 자르면 긴 막대가 됨

따라서 절단 위치 i에서 절단한 뒤, 다음에 절단할 수 있는 범위는:

$l_i \leq j \leq r_i$

여기서:

• $l_i$ = $S_j - S_i \geq X$를 만족하는 최소 j
• $r_i$ = $S_j - S_i \leq L$을 만족하는 최대 j

그림으로 이해하기

예시: $X = 7, L = 10$일 때

핵심: l과 r의 단조 증가

i가 증가하면 $S_i$도 증가하므로:

• $l_i \leq l_{i+1}$ (l은 단조 증가)
• $r_i \leq r_{i+1}$ (r도 단조 증가)

이 성질 덕분에, 모든 i에 대해 l과 r을 구하는 데 합계 0(N)이면 충분합니다 (투 포인터).

Step 4 — 판정 함수 v1: O(N²) boolean 배열

Step 3의 아이디어를 가장 단순하게 코드로 옮깁니다.

아이디어

• C[i] = "절단 위치 i에서 절단할 수 있는가?" (boolean)
• C[0] = true (왼쪽 끝은 반드시 절단)
• C[i]가 true일 때, 다음에 절단 가능한 모든 j ($l \leq j \leq r$)에 대해 C[j] = true
• 최종 답: C[N]이 true인지 확인

Java 코드 예시 - check v1 함수

static boolean checkV1(int N, long L, long[] S, long X) {
    boolean[] C = new boolean[N + 1];
    C[0] = true;

    for (int i = 0; i < N; i++) {
        if (!C[i]) continue;

        // 절단 위치 i에서 절단할 수 있으므로,
        // 다음 절단 가능한 j를 모두 탐색
        for (int j = i + 1; j <= N; j++) {
            long len = S[j] - S[i];  // i~j 사이 막대 길이
            if (len >= X && len <= L) {
                C[j] = true;
            }
        }
    }

    return C[N];
}

시간 복잡도

바깥 루프 O(N) x 안쪽 루프 O(N) = O(N²)

$N = 2 \times 10^5$일 때, $4 \times 10^{10}$ 연산으로 시간 초과입니다.

Step 5 — 판정 함수 v2: O(N²) 투 포인터 최적화

Step 4의 안쪽 루프를 개선합니다. Step 3에서 관찰한 l, r의 단조 증가 성질을 활용합니다.

핵심 변경점

Step 4에서는 각 i마다 j를 1부터 N까지 전부 탐색했습니다. 하지만:

• $l_i \leq l_{i+1}$이므로, l을 매번 처음부터 탐색할 필요가 없음
• $r_i \leq r_{i+1}$이므로, r도 마찬가지

l과 r을 전역 변수로 유지하며, 이전 값에서 이어서 증가시킵니다.

Java 코드 예시 - check v2 함수

static boolean checkV2(int N, long L, long[] S, long X) {
    int l = 0, r = 0;
    boolean[] C = new boolean[N + 1];
    C[0] = true;

    for (int i = 0; i < N; i++) {
        if (!C[i]) continue;

        // l, r은 전역 변수로 유지되므로
        // 이전 i에서의 값 이상이 자동으로 보장됨

        // l 전진: S[l] - S[i] >= X 를 만족할 때까지
        while (l <= N && S[l] - S[i] < X) l++;

        // l > N이면 더 이상 절단 불가
        if (l > N) break;

        // r 전진: S[r+1] - S[i] <= L 을 만족하는 최대 r
        while (r + 1 <= N && S[r + 1] - S[i] <= L) r++;

        // [l, r] 구간의 모든 j에 대해 C[j] = true
        for (int j = l; j <= r; j++) {
            C[j] = true;
        }
    }

    return C[N];
}

시간 복잡도 분석

• l, r의 전진: l과 r은 각각 0에서 N까지만 증가하므로, while 루프의 총 실행 횟수는 O(N)
• 내부 for 루프 (C[j] = true): 각 i에 대해 $r - l + 1$번 실행 → 최악의 경우 O(N)

전체: l, r 전진은 O(N)이지만, 내부 for 루프 때문에 여전히 O(N²)입니다.

Step 6 — 판정 함수 v3: O(N) いもす法(이모스법) 적용

Step 5의 병목(구간 일괄 갱신)을 いもす法(이모스법)으로 해결합니다.

いもす法이란?

배열의 구간 [l, r]에 일괄적으로 값을 더하는 연산을 효율화하는 기법입니다.

기본 원리

원래 배열 D와 그 누적합 배열 C의 관계를 이용합니다:

$C_i = D_0 + D_1 + \cdots + D_i$

이때 "구간 [l, r]의 모든 C에 1을 더하고 싶다"면, 원래 배열 D의 양 끝만 갱신하면 됩니다:

D[l]   += 1    ← 구간 시작
D[r+1] -= 1    ← 구간 끝 다음 (상쇄)

이후 D의 누적합을 구하면, C[l] ~ C[r]에만 1이 더해진 결과를 얻습니다.

예시로 이해하기

길이 4인 배열에서 구간 [1, 2]에 1을 더하고 싶을 때:

일반적인 방법 (O(구간 길이)):

원래 배열:   [1, 2, 3, 4]
결과:        [1, 3, 4, 4]    ← 인덱스 1, 2에 각각 +1

いもす法 (O(1)):

차분 배열 D: [1, 2, 3, 4]
갱신:        D[1] += 1, D[3] -= 1
갱신 후 D:   [1, 3, 3, 3]

누적합 C:    [0, 1, 3, 6, 10]  (갱신 전)
           → [0, 1, 4, 7, 10]  (갱신 후)

누적합 배열 C의 인덱스 2~3 (원래 배열의 인덱스 1~2에 대응)에만 1이 더해졌습니다.

Step 5 → Step 6 변환

Step 5에서 C[i]는 boolean(도달 가능 여부)이었습니다. 이를 정수로 바꿉니다:

• C[i] ≥ 1 → 절단 위치 i에서 절단 가능
• C[i] == 0 → 절단 불가

구간 갱신 for (j = l; j <= r; j++) C[j] = true를:

D[l] += 1;
D[r+1] -= 1;

로 대체하고, C는 D의 누적합으로 계산합니다.

Java 코드 예시 - check v3 함수 (최종)

static boolean checkV3(int N, long L, long[] S, long X) {
    int l = 0, r = 0;
    int[] C = new int[N + 1];  // C[i] = 절단 위치 i의 도달 가능 횟수
    int[] D = new int[N + 1];  // 차분 배열 (いもす法)

    // 초기값: 절단 위치 0은 반드시 절단 가능
    D[0] += 1;
    if (1 <= N) D[1] -= 1;

    for (int i = 0; i < N; i++) {
        // ── D의 누적합으로 C[i]를 계산 ──
        if (i > 0) {
            C[i] = C[i - 1] + D[i];
        } else {
            C[i] = D[i];
        }

        // C[i] == 0 이면 이 위치에서 절단 불가 → 스킵
        if (C[i] == 0) continue;

        // ── l 전진: S[l] - S[i] >= X 를 만족하는 최소 l ──
        while (l <= N && S[l] - S[i] < X) l++;

        // l > N이면 더 이상 절단 불가
        if (l > N) continue;

        // ── r 전진: S[r+1] - S[i] <= L 을 만족하는 최대 r ──
        while (r + 1 <= N && S[r + 1] - S[i] <= L) r++;

        // ── いもす法: 구간 [l, r]에 도달 가능 표시 ──
        D[l] += 1;
        if (r + 1 <= N) D[r + 1] -= 1;
    }

    // ── 최종 판정: C[N] > 0 이면 끝까지 도달 가능 ──
    C[N] = C[N - 1] + D[N];
    return C[N] > 0;
}

단계	코드	의미
초기화	D[0]+=1; D[1]-=1;	절단 위치 0은 항상 도달 가능
누적합	C[i] = C[i-1] + D[i]	차분 배열의 누적합으로 실제 도달 가능 여부 복원
l 전진	while S[l]-S[i] < X	최소 길이 X를 보장하는 가장 가까운 다음 절단 위치
r 전진	while S[r+1]-S[i] ≤ L	최대 길이 L을 넘지 않는 가장 먼 다음 절단 위치
いもす	D[l]+=1; D[r+1]-=1;	구간 [l, r] 전체에 도달 가능 표시 (O(1))
최종	C[N] > 0	오른쪽 끝까지 도달 가능하면 절단 방법 존재

Step 7 — 이분 탐색으로 최적값 찾기

판정 함수 check(X)가 완성되었으므로, 이제 이분 탐색으로 경계(= 최단 막대 길이의 최대값)를 찾습니다.

탐색 범위 설정

• 하한 (lo): 0 — 최솟값은 항상 0 이상
• 상한 (hi): $L + 1$ — 모든 막대가 L 이하여야 하므로, X가 L+1 이상이면 반드시 불가능

정수 이분 탐색의 특징

이 문제에서는 모든 값이 정수이므로, 실수 이분 탐색(반복 100회) 대신 정수 이분 탐색 while (hi - lo > 1) 패턴을 사용합니다.

완성 코드 예시

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        long L = sc.nextLong();
        long[] A = new long[N];
        for (int i = 0; i < N; i++) A[i] = sc.nextLong();

        // ── 누적합 전처리 ──
        long[] S = new long[N + 1];
        for (int i = 0; i < N; i++) {
            S[i + 1] = S[i] + A[i];
        }

        // ── 이분 탐색: 최솟값의 최대화 ──
        long lo = 0, hi = L + 1;
        while (hi - lo > 1) {
            long mid = (lo + hi) / 2;
            if (check(N, L, S, mid)) {
                lo = mid;   // mid 이상 가능 → 더 큰 값 탐색
            } else {
                hi = mid;   // mid 이상 불가능 → 더 작은 값 탐색
            }
        }

        // ── 출력 ──
        System.out.println(lo);
    }

    static boolean check(int N, long L, long[] S, long X) {
        int l = 0, r = 0;
        int[] C = new int[N + 1];
        int[] D = new int[N + 1];

        D[0] += 1;
        if (1 <= N) D[1] -= 1;

        for (int i = 0; i < N; i++) {
            if (i > 0) {
                C[i] = C[i - 1] + D[i];
            } else {
                C[i] = D[i];
            }

            if (C[i] == 0) continue;

            while (l <= N && S[l] - S[i] < X) l++;
            if (l > N) continue;

            while (r + 1 <= N && S[r + 1] - S[i] <= L) r++;

            D[l] += 1;
            if (r + 1 <= N) D[r + 1] -= 1;
        }

        C[N] = C[N - 1] + D[N];
        return C[N] > 0;
    }
}

이분 탐색 동작 과정 (예제 기준)

N=5, L=10, A=[3,4,1,2,4], S=[0,3,7,8,10,14]

iter 0:  lo=0,  hi=11, mid=5   → check(5)=true   → lo=5
iter 1:  lo=5,  hi=11, mid=8   → check(8)=false  → hi=8
iter 2:  lo=5,  hi=8,  mid=6   → check(6)=true   → lo=6
iter 3:  lo=6,  hi=8,  mid=7   → check(7)=true   → lo=7
iter 4:  lo=7,  hi=8   → hi-lo=1 → 종료

출력: 7 ✅

Step 8 — 계산량 분석 & 정리

시간 복잡도

부분	계산량
누적합 전처리	$O(N)$
check(X)	$O(N)$ — l, r 투 포인터 합계 O(N) + いもす法 O(1) × N
이분 탐색 반복	$O(\log L)$
전체	$O(N \log L)$

$N = 2 \times 10^5, L = 10^{15}$일 때: $2 \times 10^5 \times 50 = 10^7$ 정도의 연산으로, 시간 제한 내에 여유 있게 통과합니다.

최적화 과정 요약

Step 4: O(N²) boolean 배열
          ↓  l, r의 단조 증가 성질 활용 (투 포인터)
Step 5: O(N²) — l, r 전진은 O(N)이지만 구간 갱신 for 루프가 병목
          ↓  いもす法으로 구간 갱신을 O(1)로
Step 6: O(N) — 최종 최적화 완료! 

이 문제에서 배운 패턴

핵심 요약

항목	내용
문제 유형	최솟값의 최대화 (가장 짧은 막대의 길이 최대화)
접근법	최적화 → 판정 문제 변환 + 이분 탐색
판정 함수	누적합 + 투 포인터 + いもす法으로 O(N)
이분 탐색 타입	정수 이분 탐색 (while (hi - lo > 1))
계산량	$O(N \log L)$
핵심 테크닉	いもす法(이모스법) — 구간 일괄 갱신을 O(1)

관련 링크

• Part 1 본문: 이분 탐색 심화 — 이 문제를 포함한 3가지 이분 탐색 기법의 전체 정리
• 문제 URL: [第五回 アルゴリズム実技検定 過去問] — M - 棒の出荷
• 소스코드: tsutaj/pastbook-2-source-code (Github)