백준 2616 - 소형기관차

Java

2616 번 - 소형기관차

문제

• 소형 기관차가 정해진 객차의 수를 끈다.
• 소형 기관차가 최대로 끌 수 있는 객차의 수는 정해져있고, 그보다 많은 수의 객차를 끌 수 없다.
• 소형 기관차 3대로 최대한 많은 손님을 운송해야한다.
• 소형 기관차는 연속적으로 이어진 객차를 끌어야한다.

접근 방법

Knapsack Problem의 응용 버젼 문제였다.

각 기관차가 운용할 수 있는 객차의 수를 max라고 하자.

점화식은 다음과 같이 된다.

dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j - max] + (train[j] - train[j - max]))  

int dp[i][j]은 i번째 소형 기관차가 객차 j번째까지 보았을 때, 최대로 운송할 수 있는 구간 합 승객 수

dp[i][j-1]는 j번째 객차를 선택하지 않았을 경우, 이전 객차까지 최대 승객 수

dp[1][j-max] + (train[j] - train[j-max])은 j번째 객차를 선택했을 경우, 현재 객차를 포함하여, i-1번째 소형기관차가 객차 j-max번째까지 보았을 때 최대 승객 수 + 객차 j-max ~ j 까지의 승객 합이 된다.

max개의 칸을 운송했을 때 손님의 합(max 칸의 구간 합)은 누적합으로 해결하였다.

코드

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

public class Main {
	static int n, result, max;
	static int[] train;
	static int[][] dp;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk;
    	n = stoi(br.readLine());
    	train = new int[n + 1];
    	stk = new StringTokenizer(br.readLine());
    	for(int i = 1; i <= n; i++) {
    		train[i] = stoi(stk.nextToken()) + train[i - 1];
    	}
    	max = stoi(br.readLine());
    	
    	dp = new int[4][n + 1];
    	
    	for(int i = 1; i <= 3; i++) {
    		for(int j = i * max; j <= n; j++) {
    			dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j - max] + (train[j] - train[j - max]));
    		}
    	}
    	
    	System.out.println(dp[3][n]);
    	br.close();
	}

	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

후기

개선할 점

없습니다.