문제

• 몇 가지 역에 소형 기관차 3대를 배치한다.
• 소형 기관차가 최대로 끌 수 있는 객차의 수는 정해져있고, 그보다 많은 수의 객차를 끌 수 없다.
• 소형 기관차 3대로 최대한 많은 손님을 운송해야한다.
• 소형 기관차는 연속적으로 이어진 객차를 끌어야한다.

풀이

DP로 해결한다!

• int[] train: 기차에 탄 손님 수 저장
• int[n] sum: 1번~n번 까지의 손님 수 합 저장
• int[i][j] dp: 소형 기관차 i대로 j칸의 객차를 끌 수 있는 경우 저장
• max : 한 기관차가 끌 수 있는 최대 객차의 수

1. sum 배열에 각 칸마다 1번부터의 합을 저장한다.
2. dp배열에 각 경우의 수 저장

        for (int i = 1; i < 4; i++) {
            for (int j = i * max; j <= n; j++) {
                dp[i][j] = Math.max(
                        dp[i][j - 1],
                        dp[i - 1][j - max] + (sum[j] - sum[j - max])
                );
            }
        }

i는 소형차의 개수, j는 객차의 수를 의미한다.
max가 2일때

dp[1][2] : 소형차 1대를 가지고 2개의 객차를 끌었을 때 손님의 수
dp[1][3] : 소형차 1대를 가지고 3개의 객차를 끌었을 때 손님의 수
.
.
dp[1][7] : 
------------------------------------
dp[2][4] : 소형차 2대를 가지고 4개의 객차를 끌었을 때 손님의 수

j가 i*max부터 시작하는 이유는 소형차 2대가 운영될 때 각각 3대의 객차를 끌 수 있다면 최소 6대의 객차가 필요하기 때문이다.

그래서 dp[i][j]는 Math.max(dp[i][j-1], dp[i-1][j-max] + (sum[j] - sum[j-max])의 점화식으로 구한다.

sum[j] - sum[j-max]는 j-max칸부터 j칸까지 손님의 합이다. (max개의 칸을 운송했을 때 손님의 합)

소스 코드

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

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

        int n = Integer.parseInt(br.readLine());
        int[] train = new int[n + 1];
        int[] sum = new int[n + 1];
        int[][] dp = new int[4][n + 1];

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

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

        for (int i = 1; i < 4; i++) {
            for (int j = i * max; j <= n; j++) {
                dp[i][j] = Math.max(
                        dp[i][j - 1],
                        dp[i - 1][j - max] + (sum[j] - sum[j - max])
                );
            }
        }

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

DP는 어려워.. ㅜㅜ
점화식 세우는 거 아직 너무 어렵다 곧 정복하기..