백준 4008 특공대 JAVA 풀이 (DP, CHT, 누적합, 시간복잡도)

🔗 문제 링크 

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

---

📌 문제 개요

병사들을 연속된 구간으로 나누고,
각 구간의 합을 x라고 할 때 ax² + bx + c의 점수를 계산하여
전체 점수의 최댓값을 구하는 문제

 

단순하게 모든 구간을 고려하면 시간복잡도가 O(N²)이 되어
N = 1,000,000에서 절대 풀 수 없다.

---

📌 접근 방법

이 문제의 핵심은 DP + 식 변형 + CHT 최적화입니다.

먼저 누적합을 정의합니다.

• S[i] = x1 + x2 + ... + xi

그러면 구간 합은 다음처럼 계산됩니다.

• 구간 합 = S[i] - S[j]

이제 DP를 정의합니다.

• dp[i] = 1 ~ i까지 최대 점수

점화식: dp[i] = max(dp[j] + f(S[i] - S[j]))

 

여기서 그대로 계산하면 O(N²)이므로,
식을 전개해서 최적화해야 합니다.

---

📌 핵심 아이디어

식을 전개하면 다음과 같습니다.

dp[i]
= aS[i]^2 + bS[i] + c
+ max( (-2aS[j]) * S[i] + (dp[j] + aS[j]^2 - bS[j]) )

 

여기서 중요한 포인트:

• j마다 하나의 직선을 만들 수 있음
• 현재 x = S[i]에서 최대값을 찾는 문제로 변환됨

직선 정의

• 기울기 m = -2aS[j]
• 절편 k = dp[j] + aS[j]^2 - bS[j]

"직선 중에서 x에서 최대값 찾기 문제" → CHT 적용

---

📌 처리 흐름

입력
→ 누적합 S 계산
→ CHT 초기 직선 추가 (j=0)
→ i = 1 ~ N 반복
→ query(S[i])로 최적값 찾기
→ dp[i] 계산
→ 새로운 직선 추가
→ dp[N] 출력

---

📌 전체 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

import java.io.*;
import java.util.*;

public class Main {

    static class Line {
        long m, b;
        Line(long m, long b) {
            this.m = m;
            this.b = b;
        }
    }

    static class CHT {
        ArrayList<Line> lines = new ArrayList<>();
        int ptr = 0;

        // l2가 필요 없는지 판단 (double 없이 처리)
        boolean isBad(Line l1, Line l2, Line l3) {
            return (l3.b - l1.b) * (l1.m - l2.m)
                    <= (l2.b - l1.b) * (l1.m - l3.m);
        }

        void add(long m, long b) {
            Line newLine = new Line(m, b);

            while (lines.size() >= 2 &&
                    isBad(lines.get(lines.size() - 2),
                            lines.get(lines.size() - 1),
                            newLine)) {
                lines.remove(lines.size() - 1);
            }

            lines.add(newLine);

            if (ptr >= lines.size()) ptr = lines.size() - 1;
        }

        long query(long x) {
            if (ptr >= lines.size()) ptr = lines.size() - 1;

            while (ptr + 1 < lines.size() &&
                    lines.get(ptr + 1).m * x + lines.get(ptr + 1).b
                            >= lines.get(ptr).m * x + lines.get(ptr).b) {
                ptr++;
            }

            return lines.get(ptr).m * x + lines.get(ptr).b;
        }
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());

        long a = Long.parseLong(st.nextToken());
        long b = Long.parseLong(st.nextToken());
        long c = Long.parseLong(st.nextToken());

        long[] S = new long[N + 1];
        long[] dp = new long[N + 1];

        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            S[i] = S[i - 1] + Long.parseLong(st.nextToken());
        }

        CHT cht = new CHT();

        // 초기 직선 (j = 0)
        cht.add(0, 0);

        for (int i = 1; i <= N; i++) {
            long x = S[i];

            long best = cht.query(x);

            dp[i] = a * x * x + b * x + c + best;

            long m = -2 * a * x;
            long k = dp[i] + a * x * x - b * x;

            cht.add(m, k);
        }

        System.out.println(dp[N]);
    }
}

---

📄 정리

백준 4008번은 단순 DP처럼 보이지만,
실제로는 누적합 + 식 전개 + CHT 최적화가 핵심인 문제

• 구간 합은 누적합 차이로 바꾼다
• dp[i] = max(dp[j] + 구간점수) 형태를 세운다
• 식을 전개해서 직선의 최대값 문제로 변형한다
• CHT를 이용해 빠르게 최적값을 찾는다