[백준/DP] 2616 소형기관차 - 자바

(obsidian 기록일 : 24년 1월 1일)

문제

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

2616번: 소형기관차

---

풀이

변수선언

• int[i] trainGuest : 기차탄 손님
• int[i] guestSum : 기차탄 손님 누적합
• int[i][j] dp : 소형기관차 i개로 j칸을 끌고갈 때 최대로 운송할 수 있는 손님의 수
• M : 한개의 소형 기관차가 끌 수 있는 최대 객차의 수

 

예시 입력값

N = 7, M = 2

손님수	35	40	50	10	30	45	60
누적합	35	75	125	135	165	210	270

 

객차에 승객 수는 두 조건으로 나눌 수 있다.

1. dp[i][j - 1] >= j 번째 객차를 선택하지 않을시 이전객차의 최대 승객수

2. dp[i - 1][j - m] + (guestSum[j] - guestSum[j - m]) : j번째 객차 선택...

즉, i-1개 소형기관차 선택시에 첫번째 객차부터 j-m 까지 인원채대 승객 합 + j - m 부터 j 까지의 승객합을 나타냄.

 

점화식은 그러므로 다음과 같다 dp[i][j] = Math.max(1번 조건, 2번 조건)

 

import java.io.*;
import java.util.*;

public class BOJ_2616_G3_소형기관차 {
    static int n, m;
    public static void main(String[] args) throws Exception {
        // start :: input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        int[] trainGuest = new int[n + 1];
        int[] guestSum = new int[n + 1];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= n; i++) {
            trainGuest[i] = Integer.parseInt(st.nextToken());
            guestSum[i] = trainGuest[i] + guestSum[i - 1];
        }
        m = Integer.parseInt(br.readLine());
        int[][] dp = new int[4][n+1];
        int ans = 0;
        // end :: input

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

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

}