[백준 Baekjoon] 2616번 소형기관차 - JAVA

백준 Baekjoon 2616번 소형기관차 - JAVA

---

문제 풀이

다이나믹 프로그래밍과 누적합을 사용하여 푸는 문제이다. 제한사항의 기관차의 수가 그리 크지 않어 dfs탐색으로도 풀 수는 있을거 같지만, 시간이 오래걸리고 문제에서 원하는 풀이 방식은 아닌듯 했다.

 

누적합을 사용하여 뒤에 DP에서 기관차가 끌 수 있는 최대 객차의 수의 승객의 합을 쉽게 구할 수 있다.

 

DP의 점화식은 다음과 같다. dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j - max] + sum[j] - sum[j - max])
i를 1 ~ 3 범위로 증가 시키며 각 숫자의 기관차가 운송할 수 있는 최대의 손님 수를 구한다.
j를 i * max의 범위부터 시작하는데, 예시로 주어진 문제를 예로 들어 기관차가 1대일 때는 최소 2대의 객차가 필요하고, 2대일 때는 4대의 객차가 필요하기 때문이다.

점화식은 이전 기관차(i - 1)가 해당 기관차가 운송할 수 있는 인원 수 이전(j - max)까지 운송할 수 있는 최대 값과, 같은 범위에서 해당 기관차가 운송할 수 있는 인원의 합을 누적합을 통해 구해 더한값과, 해당 기관차(i)의 앞의 칸까지 구한 최대 운송 인원(j - 1) 중 최대값을 구해 저장한다.

 

문제에서 주어진 예시로 누적합과, DP를 구하면 다음과 같다.

누적합	0	1	2	3	4	5	6	7
	0	35	75	125	135	165	210	270

DP	0	1	2	3	4	5	6	7
1	0	0	75	90	90	90	90	105
2	0	0	0	0	135	135	165	195
3	0	0	0	0	0	0	210	240

소스 코드

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

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

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

        int[] train = new int[N + 1];
        int[] sum = new int[N + 1];

        StringTokenizer 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());

        int[][] 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], dp[i - 1][j - max] + sum[j] - sum[j - max]);
            }
        }

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