[BOJ] 백준 2616번 소형기관차 (Java)

#2616 소형기관차

난이도 : 골드 5

유형 : DP / 누적합 

2616번: 소형기관차

▸ 문제

기차는 맨 앞에 있는 기관차 1대가 손님이 탄 객차 여러 칸을 끌고 간다. 기관차가 고장나면 기차를 운행할 수 없게 되므로 최근 철도청은 기관차 고장에 대비하여 몇몇 역에 소형 기관차 3대를 배치하기로 결정하였다. 소형 기관차는 평소에 이용하는 기관차보다 훨씬 적은 수의 객차만을 끌 수 있다.

기관차가 고장났을 때 끌고 가던 객차 모두를 소형 기관차 3대가 나누어 끌 수 없기 때문에, 소형 기관차들이 어떤 객차들을 끌고 가는 것이 좋을까하는 문제를 고민하다가 다음과 같이 하기로 결정하였다.

1. 소형 기관차가 최대로 끌 수 있는 객차의 수를 미리 정해 놓고, 그보다 많은 수의 객차를 절대로 끌게 하지 않는다. 3대의 소형 기관차가 최대로 끌 수 있는 객차의 수는 서로 같다.
2. 소형 기관차 3대를 이용하여 최대한 많은 손님을 목적지까지 운송하도록 한다. 각 객차 마다 타고 있는 손님의 수는 미리 알고 있고, 다른 객차로 손님들이 이동하는 것은 허용하지 않는다.
3. 각 소형 기관차는 번호가 연속적으로 이어진 객차를 끌게 한다. 객차는 기관차 바로 뒤에 있는 객차부터 시작하여 1번 부터 차례로 번호가 붙어있다.

예를 들어 기관차가 끌고 가던 객차가 7칸이고, 소형 기관차 1대가 최대로 끌 수 있는 객차 수는 2칸이라고 하자. 그리고 1번 부터 7번까지 각 객차에 타고 있는 손님의 수가 아래 표와 같다고 하자. 괄호속에 있는 숫자는 객차 번호를 나타낸다.

소형 기관차 3대는 각각 1-2번, 3-4번, 그리고 6-7번 객차를 끌고 가면 손님 240명을 운송할 수 있고, 이보다 많은 수의 손님을 운송할 수 없다.

기관차가 끌고 가던 객차의 수와 각 객차에 타고 있던 손님의 수, 그리고 소형 기관차가 최대로 끌수 있는 객차의 수가 주어질 때, 소형 기관차 3대를 이용하여 최대로 운송할 수 있는 손님 수를 구하는 프로그램을 작성하시오.

▸ 입력

첫째 줄에 기관차가 끌고 가던 객차의 수가 입력된다. 그 수는 50,000 이하이다. 둘째 줄에는 기관차가 끌고 가던 객차에 타고 있는 손님의 수가 1번 객차부터 차례로 입력된다. 한 객차에 타고 있는 손님의 수는 100명 이하이고, 입력되는 숫자들 사이에 빈칸이 하나씩 있다. 셋째 줄에는 소형 기관차가 최대로 끌 수 있는 객차의 수가 입력된다. 그 수는 기관차가 끌고 가던 객차 수의 1/3보다 적다.

▸ 출력

한 줄에 소형 기관차 3대를 이용하여 최대로 운송할 수 있는 손님 수를 출력한다.

 

문제 풀이

소형기관차 3대로 한 기관차에 있는 객차를 나누어 최대로 운송할 수 있는 손님의 수를 구하는 문제이다. 

 

누적합 배열을 만들 생각을 못하고 for문안에서 합을 구해서 좀 헤매었다. 풀이를 참고하여 누적합방식을 보고 바로 풀 수 있었다. DP를 사용하여 배열을 3부분으로 나누어 최대 누적합을 구하면 된다.

 

누가봐도 bottom-up인 문제이면 접근방식을 다음과 같이하자.

→ 하위 문제를 뚫어지게 쳐다본다 😳

→ dp 메모이제이션할 배열 데이터를 생각하자 (몇차원 배열을 사용해야되는지 > 소형기관차 수, 객차의 수)

→ (combine) 하위문제를 상위문제로 결합시키는 방식을 생각한다.  (언제 값을 갱신하고 결합해야 하는지 > (j>=len)일때, dp[i][j]값 갱신)

→ 어떤 반복구조로 담아야할 지 생각하고 for문을 짜자. (루프의 범위를 어떻게 몇중으로 돌려야 하는지 > 소형기관차 1~3, 객차 1~n)

 

☛ 이래도 하위문제가 너무 복잡해서 점화식이 잘 안나온다 싶으면 top-down으로 풀자 😅

 

📚 조건

   ∙ 객차의 수 ( 1 ~ 50,000 )

   ∙ 한 객차 인원 수 100명 이하

   ∙ 소형 기관차가 최대로 끌 수 있는 객차의 수를 넘으면 안되고 각 소형기관차가 최대로 끌 수 있는 객차의 수는 같다.

   

1) sum[] 배열에 1~n 구간의 누적합을 저장한다.

sum[0] = 0;
for(int i=0; i<n; i++) {
	sum[i+1] = sum[i] + train[i];
}

 

2) dp[i][j]에 최댓값 갱신하여 저장하기

i : 소형기관차 수,  j : 객차 칸 번호

 

if(j>len) : 최댓값을 저장하기 위해서는 객차 칸의 수(j)가 len보다 클 때 값을 비교해준다.

 

dp[i][j-1] : 새로운 값이 이전 값보다 크지않으면 이전 값 그대로 dp[i][j]에 저장

 

dp[i-1][j-len] : i-1개 소형기관차를 사용하여 객차 1 ~ j-len까지 인원 최대 누적합

sum[j] - sum[j-len] : j-len+1 ~ j까지의 손님 누적합

if(j >= len) {
	dp[i][j] = Math.max(dp[i][j-1], dp[i-1][j-len] + (sum[j] - sum[j-len]));
}

 

 

풀이 코드 

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

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		int[] train = new int[n];
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=0; i<n; i++) {
			train[i] = Integer.parseInt(st.nextToken());
		}
		
		int len = Integer.parseInt(br.readLine());
		int[] sum = new int[n+1];
		sum[0] = 0;
		for(int i=0; i<n; i++) {
			sum[i+1] = sum[i] + train[i];
		}
		
		int[][] dp = new int[4][n+1];
		int res = 0;
		for(int i=1; i<4; i++){
			for(int j=1; j<n+1; j++) {
				dp[i][j] = 0;
				if(j >= len) {
					dp[i][j] = Math.max(dp[i][j-1], dp[i-1][j-len] + (sum[j] - sum[j-len]));
				}
				res = Math.max(dp[i][j], res);
			}
		}
		System.out.println(res);
	}
}