백준 2615: 소형기관차(Java)

🚆 백준 2616번: 소형기관차

🎯 문제 요약

• N개의 객차(1 ≤ N ≤ 50,000)가 수직선 상에 있다.
• 각 객차에는 손님이 타고 있다 (최대 100명).
• 소형 기관차는 최대 K칸까지 끌 수 있으며, 총 3대가 존재한다.
• 3개의 소형 기관차가 서로 겹치지 않게 총합 손님 수가 최대가 되도록 운행할 때의 최대 손님 수를 구하라.

---

🧠 문제 접근

✅ 핵심 개념

• 3개의 기관차가 끌 수 있는 객차를 비중복으로 선택 → 구간 합 최적화
• 누적합 + DP 사용
• dp[i][j]: i번째 기관차까지 사용해서, j번째 객차까지 탐색했을 때 최댓값

---

🔍 알고리즘 설계

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        int[] people = new int[N + 1];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            people[i] = Integer.parseInt(st.nextToken());
        }

        int K = Integer.parseInt(br.readLine());

        int[] total = new int[N + 1];
        for (int i = 1; i <= N; i++) {
            total[i] = total[i - 1] + people[i];
        }

        int[][] dp = new int[4][N + 1];

        for (int i = 1; i <= 3; i++) {
            for (int j = K * i; j <= N; j++) {
                int curtotal = total[j] - total[j - K];
                dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j - K] + curtotal);
            }
        }

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

---

✅ 시간 복잡도

• 누적합 계산: O(N)
• DP 테이블 채우기: O(N)
• 전체 시간복잡도: O(N) → N ≤ 50,000 이므로 충분히 통과 가능

---

💡 정리

• 핵심은 비중복 구간 합 최적화 문제를 DP + 누적합으로 해결하는 것
• 상태 전이: dp[i][j] = max(dp[i][j - 1], dp[i - 1][j - K] + sum(j-K+1 ~ j))
• 알고리즘 구현 난이도는 낮지만, 상태 정의를 이해하는 것이 중요하다