[BaekJoon] 2616 소형기관차 (Java)

1.  문제 링크

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

2.  문제

요약

• 기차는 맨 앞에 있는 기관차 1대가 손님이 탄 객차 여러 칸을 끌고 가는데, 기관차가 고장나면 기차를 운행할 수 없게 되므로 몇몇 역에 소형 기관차 3대를 배치하였습니다.
• 소형 기관차는 평소에 이용하는 기관차보다 훨씬 적은 수의 객차만을 끌 수 있습니다.
• 기관차가 고장났을 때 객차 모두를 소형 기관차 3대가 나누어 끌 수 없어, 소형 기관차들이 어떤 객차들을 끌고 가는 것이 좋을까하는 문제에 대해 다음과 같이 하기로 결정하였습니다.
  1. 소형 기관차가 최대로 끌 수 있는 객차의 수를 미리 정해놓고, 그보다 많은 수의 객차를 절대로 끌게 하지 않습니다. 3대의 소형 기관차가 최대로 끌 수 있는 객차의 수는 서로 같습니다.
  2. 소형 기관차 3대를 이용하여 최대로 많은 손님을 목적지까지 운송합니다. 각 객차마다 타고 있는 손님의 수는 미리 알고 있고, 다른 객차로 손님들이 이동하는 것을 허용하지 않습니다.
  3. 각 소형 기관차는 번호가 연속적으로 이어진 객차를 끌게 합니다. 객차는 기관차 바로 뒤에 있는 객차부터 시작하여 1번부터 차례로 번호가 붙어있습니다.
• 기관차를 끌고 가던 객차의 수와 각 객차에 타고 있던 손님의 수, 그리고 소형 기관차가 최대로 끌 수 있는 객차의 수가 주어질 때, 소형 기관차 3대를 이용하여 최대로 운송할 수 있는 손님 수를 구하는 문제입니다.
• 입력: 첫 번째 줄에 50,000보다 작거나 같은 기관차가 끌고 가던 객차의 수가 입력되고 두 번째 줄에 100보다 작거나 같은 기관차가 끌고 가던 객차에 타고 있는 손님의 수가 1번 객차부터 입력됩니다. 세 번째 줄에 기관차가 끌고 가던 객차의 수의 1/3보다 적은 소형 기관차가 최대로 끌 수 있는 객차의 수가 주어집니다.
• 출력: 첫 번째 줄에 소형 기관차 3대를 이용하여 최대로 운송할 수 있는 손님의 수를 출력합니다.

3.  소스코드

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

public class Main {
    static final int LOCOMOTIVENUM = 3;
    static int passengerCarNum, maxPullNum;
    static int[] guestNum, prefixSum;
    static int[][] dp;

    static void input() {
        Reader scanner = new Reader();

        passengerCarNum = scanner.nextInt();
        guestNum = new int[passengerCarNum + 1];
        prefixSum = new int[passengerCarNum + 1];

        for(int idx = 1; idx <= passengerCarNum; idx++) {
            guestNum[idx] = scanner.nextInt();
            prefixSum[idx] = prefixSum[idx - 1] + guestNum[idx];
        }

        maxPullNum = scanner.nextInt();
    }

    static void solution() {
        dp = new int[LOCOMOTIVENUM + 1][passengerCarNum + 1];

        for(int locomotive = 1; locomotive <= LOCOMOTIVENUM; locomotive++)
            for(int passengerCar = locomotive * maxPullNum; passengerCar <= passengerCarNum; passengerCar++) {
                dp[locomotive][passengerCar] = Math.max(dp[locomotive][passengerCar - 1],
                        dp[locomotive - 1][passengerCar - maxPullNum] + prefixSum[passengerCar] - prefixSum[passengerCar - maxPullNum]);
        }

        System.out.println(dp[LOCOMOTIVENUM][passengerCarNum]);
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }

            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}

4.  접근

변수 선언

• LOCOMOTIVENUM : 소형 기관차의 개수
• passengerCarNum : 객차의 개수
• maxPullNum : 소형 기관차가 최대로 끌 수 있는 객차의 수
• guestNum : 각 객차에 타고 있는 손님의 수를 나타내는 배열
• prefixSum : guestNum 배열에 대한 누적 합을 나타내는 배열
• dp : 메모이제이션을 위한 2차원 배열
  • dp[x][y] : x개의 소형 기관차가 y번 객차까지 (x * maxPullNum)대의 객차를 끌 때 최대로 운송할 수 있는 손님의 수

풀이

• 주어진 입력들을 받으면서 guestNum 및 prefixSum의 값을 채웁니다.
• 메모이제이션을 이용해 최대로 운송할 수 있는 손님의 수를 구합니다.
  • 누적합을 구해놨으므로 우리가 원하는 구간에 대한 손님 수의 합을 구할 수 있습니다.
  • x개의 소형 기관차가 y번 객차까지 (x * maxPullNum)대의 객차를 끌 때 최대로 운송할 수 있는 손님의 수는 두 값을 비교하여 더 큰 값을 구하면 됩니다.
    1. x개의 소형 기관차가 (y - 1)번 객차까지 (x * maxPullNum)대의 객차를 끌 때 최대로 운송할 수 있는 손님의 수
    2. 한 대의 소형 기관차가 (y - 1번 객차, y번 객차)를 끌 때
       • 현재 탐색하는 소형 기관차가 (y - 1번 객차, y번 객차)를 끈다면 x개의 소형 기관차는 1번 객차부터 y - 2번 객차까지 ((x - 1) * maxPullNum)대의 객차를 끌게 됩니다.
       • 그렇다면 결국 이 경우에는 dp[x - 1][y - 2] + (prefixSum[y] - prefixSum[y - 2])명의 사람을 운송하게 됩니다.
    • 두 값 중 큰 값이 현재까지 운송할 수 있는 손님의 최댓값이 됩니다.
      • dp[x][y] = max(dp[x][y - 1], dp[x - 1][y - 2] + (prefixSum[y] - prefixSum[y - 2]))
      
      
  • 위 점화식을 이용하여 소형 기관차가 1대일 때부터 3대일 때까지 dp 배열을 채워나갑니다.
  • 모두 채운 후에 dp[LOCOMOTIVENUM][passengerCarNum]가 문제의 답이 됩니다.