[BOJ] 2616. 소형기관차

[작성일]

• 2022-03-08

[분류]

• 누적합
• dp
  
  
  

[문제링크]

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

[요구사항]

• 소형 기관차 3대를 이용하여 최대로 운송할 수 있는 손님 수를 구하는 프로그램을 작성하시오.
  
  
  

[풀이]

누적합을 사용해야겠다는 생각은 들었는데 dp문제는 많이 안 풀어봐서 그런지 도저히 생각이 나지 않아서 다른 풀이를 참고하였다.

우선 train 1차원 배열에 입력 값을 모두 받았다.
이후, sum 1차원 배열에 1 ~ n까지의 누적합을 넣어주었다.

이제, dp 배열을 이용하여 정답을 구했다.
dp는 2차원 배열인데, i는 소형차의 개수, j는 객차의 수로 둔다.

소형차 개수가 최대 3개이기 때문에 최소 1개에서 최대 3개까지 반복한다.
j의 시작점은 i*M(M은 여기서 소형차가 끌 수 있는 최대 객차 개수)부터 시작한다.
왜냐하면 더 작을 경우에 조건에 만족하지 않기 때문이다.
이후 j를 1씩 증가시키면서

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

의 식을 만족하도록 dp를 갱신한다.

dp[i][j - 1]의 의미는 바로 전 값이다.
dp[i - 1][j - M] + sum[j] - sum[j - M]은 객차가 운송할 수 있는 만큼 전의 값 + 그 이후부터 현재 j까지의 객차 손님수의 합이다.

둘 중 더 큰 값으로 갱신해주면서 진행하면 배열의 가장 끝 값이 정답이 된다.

[코드]

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

class Main {
    static int N, M;
    static int[] train;
    static int[] sum;
    static int[][] dp;
    static long ans = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        train = new int[N + 1];
        sum = new int[N + 1];
        dp = new int[4][N + 1];

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

        // 누적합 구하기
        for (int i = 1; i <= N; i++) {
            sum[i] = sum[i - 1] + train[i];
        }

        // dp로 해결
        for (int i = 1; i < 4; i++) { // 소형차 개수
            for (int j = i * M; j <= N; j++) { // 몇 개의 객차를 끌까
                dp[i][j] = Math.max(
                        dp[i][j - 1],
                        dp[i - 1][j - M] + sum[j] - sum[j - M]
                );
            }
        }

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