[BOJ 2616] 소형 기관차 - java

2616번: 소형기관차

1. 테이블 정의

dp[i][j]

👉 소형기관차 i 대로 j 칸의 객차를 끌 때의 최대 탑승 고객 수

ex) dp[2][5] ⇒ 소형 기관차 2대가 있고, 객차는 1 ~ 5번만 존재하는 상황

2. 점화식 찾기

dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j - max] + (sum[j] - sum[j - max]);

dp[2][5]를 생각해 보면,

여기서 j = i * max 부터인 이유는 소형 기관차가 i대 있을 때, 최소 i * max 개의 객차는 끌기 때문!

코드

package DP;

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

// 백준 2616번: 소형 기관차
public class 소형기관차 {

    static int n; // 객차의 수
    static int[] sum; // 객차별 손님 수 배열의 누적합
    static int max; // 소형 기관차 1대가 끌 수 있는 객차의 수
    static int[][] dp;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());

        sum = new int[n + 1];
        for (int i = 1; i <= n; i++) { // 누적합
            sum[i] = Integer.parseInt(st.nextToken()) + sum[i - 1];
        }
        max = Integer.parseInt(br.readLine());
        dp = new int[4][n + 1];

        for (int i = 1; i <= 3; i++) {
            for (int j = i * max; j <= n; j++) {
                dp[i][j] = Math.max(
                    dp[i][j - 1], // (j - max + 1) ~ (j) 번 열차를 안 끄는 경우
                    dp[i - 1][j - max] + (sum[j] - sum[j - max])
                    // (j - max + 1) ~ (j) 번 열차를 포함하기 때문에,
                    // (j - max + 1) ~ (j) 번 열차의 승객 합 더하고
                    // (j - max + 1) ~ (j) 번 열차를 포함하지 않았을 때의 dp 값 가져온다!
                );
            }
        }
        System.out.println(dp[3][n]);
    }
}