[백준] 2616번 - 소형기관차 (Java)

문제

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

2616번: 소형기관차

---

알고리즘

다이나믹 프로그래밍 (DP), 누적합

 

우선, 각 열차의 승객의 누적합을 구해둔다. 계산식을 단순화하여 계산 속도를 빠르게 하기 위함의 목적이다.

 

그 다음 dp 배열을 세운다.

dp[i][j] : 소형 기관차 i개로 j번째 칸까지 살펴봤을 때, 그 시점에서 최대로 운송할 수 있는 손님의 수

예를 들어, 객실 칸이 1~9번까지 있다고 해보자. dp[2][6]은 소형 기관차 2대로 1번부터 6번까지 객실까지만 한정할 때, 운송할 수 있는 최대 손님의 수를 의미한다. dp[1][3]하면 소형 기관차 1대로 1~3번까지 객실만 한정할 때, 운송할 수 있는 최대 손님 수이다. 그러면, 이때 답은 dp[3][9]를 출력하면 된다. 우리가 원하는 답은 소형기관차 3대를 가지고 모든 객실을 둘러봤을때 최대 손님수이기 때문이다.

 

max : 소형기관차가 끌 수 있는 최대 객실의 수라고 한다면 우리는 점화식을 두조건으로 나누어서

dp[i][j] = Math.max(dp[i][j-1], dp[i-1][j-max] + (sum[j] - sum[j-max]))로 세울 수 있다.

dp[i][j-1] : j번째 객차까지 범위를 한정하기 전에, 이전 객차의 최대 승객수. 즉, j번째 객차를 선택하지 않을 경우

dp[i-1][j-max] + (sum[j] - sum[j-max]) : j번째 객차까지를 끌고 가기로 선택했을 경우이다. 객차는 반드시 max개의 객실을 끌고 갈 것이다. (최대한 손님을 많이 끌고가야되니깐 최대한 많은 객실을 끌고가야됨) 따라서, 이전 객차의 최댓값을 가져올 때는 j - max 까지 봤을때로 비교해야 한다. 이게 무슨 말인지 예시로 설명해보고자 한다.

ex) 객실이 1~6번까지 있다고 해보자. 그래고 max가 2라고 해보자. 소형 기관차 2번이 4번 객실까지 끌고 가기로 결심했다. (dp[2][4]에 값을 저장한다는 뜻) 그러면 소형 기관차 1번의 최댓값을 가져와서 갱신해줘야되는데, 만약 dp[1][3]의 값을 가져오면 어떻게 될까? dp[1][3]에 3번 객실까지 끌고가기로 결심한 값을 들고오면? 문제 조건 3번에 의해서 기관차는 반드시 연속한 칸을 끌고 가야되므로 1번 기관차는 2번 객실과 3번 객실을 끌고갈 것이다. 하지만, 소형기관차 2번이 4번 객실까지 끌고 가기로 결심했다는 것은 3번과 4번 객실을 끌고 간다는 의미이다. 기관차 1번이 이미 3번 객실을 끌고 갔는데 또다시 2번 기관차가 3번 객실을 끌고 갈 수 없는 것이다.

 

즉, dp[i-1][j-max] + (sum[j] - sum[j-max])의 의미는 i-1번째 소형 기관차가 j-max 번째 객실까지 봤을때 손님 최댓값에 (j-max + 1)번째 객실 ~ j번째 객실 까지 승객합을 나타낸다. 그래서 두 경우를 Math.max를 이용해 최댓값 비교해주면 끝난다.

 

참고로, j가 i*max 부터 시작하는 이유는 위에 예시를 잘 읽어보면 알 수 있을 것이다. 소형기관차가 2대 운영 될 때, 각각 최대 3대 객차를 끌 수 있으면, 최소 6대의 객차가 필요하기 때문이다.

---

코드

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

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[] customer = new int[n + 1];
        int[] sum = new int[n + 1];

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

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

        int[][] dp = new int[4][n + 1];
        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]);

    }
}