[백준 2616] 소형기관차 (java)

문제풀이

 dp를 이용해서 푸는 문제이다.

 

문제가 어려워서 다른 풀이를 참고하였다

 

이전 객차까지의 최댓값(dp[i][j-1])과 현재 객차를 포함했을 때의 최댓값(sum[j] - sum[j-maxLength]) + dp[i-1][j-maxLength]) 중 큰 값이 현재.i번째 기관차가 1~j객실중 끌 수 있는 승객의 최댓값이 된다.

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Baekjoon2616 {
 
    static int[][] dp;
    static int[] train, sum;
    static int maxLength=0;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int numOfCarriage = Integer.parseInt(st.nextToken());
 
        train = new int[numOfCarriage+1];
        st = new StringTokenizer(br.readLine());
        sum = new int[numOfCarriage+1];
        for(int i=1;i<=numOfCarriage;i++){
            train[i] = Integer.parseInt(st.nextToken());
            sum[i] = sum[i-1]+train[i];
        }
 
        maxLength = Integer.parseInt(br.readLine());
        dp = new int[4][numOfCarriage+1];
 
        for(int i=1;i<4;i++){
            for(int j=i*maxLength;j<=numOfCarriage;j++){
                dp[i][j] = Math.max(dp[i][j-1],(sum[j]-sum[j-maxLength])+ dp[i-1][j-maxLength]);
            }
        }
        System.out.println(dp[3][numOfCarriage]);
 
 
    }
}
 

문제 링크 : www.acmicpc.net/problem/2616