BOJ2616 소형기관차(Java)

---

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

풀이 방법 : DP

---

사고 과정

길이 N인 객차들을 적절히 3분할 해서 최대 승객 수를 구해보자.

뭔가 누적 합으로 한 번에 I~J의 승객 수를 한 번에 구할 수 있도록 해야겠다는 생각이 든다.

DP[i][j] = i번 칸의 객실까지, 0~j번 열차가 끌 때 최대 수송량.

0번 열차가 i번까지 수송 가능한 최대 객실이 k라고 하면,

1번 열차가 i + M번까지 끌 때 최대 수송량은 (k + (1번열차가 i부터 i + M까지 끌 때의 수))이다.

2번열차는 1번열차에 대해 같은 연산을 하면 될 것이다.

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.List;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder sb = new StringBuilder();
    static StringTokenizer st;

    static int N, M;
    static int [] sum = new int [50001];
    static int [][] dp = new int [50001][3];
    static int ans;

    static void solve() {
        for(int i = 1; i <= M; i++) {
            dp[i][0] = sum[i];
        }
        for (int i = M + 1; i <= N; i++) {
            dp[i][0] = Math.max(dp[i - 1][0], sum[i] - sum[i - M]);
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - M][0] + sum[i] - sum[i - M]);
            dp[i][2] = Math.max(dp[i - 1][2], dp[i - M][1] + sum[i] - sum[i - M]);
        }
        ans = dp[N][2];
    }

    public static void main(String[] args) throws NumberFormatException, IOException {

        N = Integer.parseInt(br.readLine().trim());

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

        }
        M = Integer.parseInt(br.readLine().trim());

        solve();

        System.out.println(ans);
    }
}