아이디어

• 문제가 중복 부분문제 구조를 가진다. DP를 적용해보자.
• 1 ~ i 구간 중에서 길이 L의 기관차 k개 놓았을 때 최대 부분합 f(k, i)은, i번에서 끝나도록 L개를 연속해서 선택하는 경우와 아닌 경우로 나뉜다.
  • 첫 번째 경우는 1 ~ i-L 구간에서 k-1개를 놓고, i-L+1 ~ L번 칸의 승객 수를 취하는 것과 같다.
    (이때 i-L+1 ~ L 구간의 부분합을 PS[i] (← partial sum)이라 하자.)
  • 두 번째 경우는 이전 선택(1 ~ i-1 구간에서 k개를 선택하는 것)과 같다.
• 두 경우 중 최댓값을 취하면 부분문제의 답을 구할 수 있다. 식으로 쓰면 다음과 같다.
  f(k, i) = max(f(k, i-1), PS[i] + f(k, i - L))
• 계산 속도를 높이기 위해 부분합 PS[i]를 미리 구해놓자. 부분합은 누적합의 차로 구할 수 있다.
  • 즉, 1 ~ i까지의 누적합을 PA[i](← passenger accumulated)라 하면 PS[i] = PA[i] - PA[i-L]다.
• 최종적으로 우리가 구하고자 하는 답은 f(3, N)이다.

코드

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

// 시, 공간복잡도 O(N^2) 이하
public class Main {
	static BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer tk = null;
	
	static int N;		// 객차 수
	static int[] PA;	// 승객 누적 합
	static int L;		// 기관차 한대가 끌 수 있는 최대 객차 수
	
	static int[] PS;	// i-L+1~i 까지의 부분합
	static int memo[][];
	
	public static void main(String[] args) throws Exception {
		N = Integer.parseInt(rd.readLine());
		
		PA = new int[N + 1];
		tk = new StringTokenizer(rd.readLine());
		for (int i=1; i<=N; i++)
			PA[i] = PA[i-1] + Integer.parseInt(tk.nextToken());
		memo = new int[4][N+1];
		
		L = Integer.parseInt(rd.readLine());
		PS = new int[N+1];
		for (int i=L; i <= N; i++)
			PS[i] = PA[i] - PA[i-L];
		
		for (int i=1; i<=3; i++) {
			for (int j=i*L; j <= N; j++) {
				memo[i][j] = Math.max(memo[i][j-1], PS[j] + memo[i-1][j - L]);
			}
		}
		
		System.out.println(memo[3][N]);
	}
}

메모리 및 시간

• 메모리: 19516 KB
• 시간: 216 ms

리뷰

• 처음에 memo의 정의를 i번부터 '시작'하는 구간의 부분해로 보았다가 역순으로 탐색하는 바람에 인덱스 처리가 상당히 더러웠던 문제
• 육각수 때도 느꼈지만, 어려운 DP일 수록 점화식을 도출하는 것이 어렵다.

최초 풀이 코드

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

// 시, 공간복잡도 O(N^2) 이하
public class Main {
	static BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer tk = null;
	
	static int N;		// 객차 수
	static int[] PA;	// 승객 누적 합
	static int L;		// 기관차 한대가 끌 수 있는 최대 객차 수
	
	static int memo[][];
	
	public static void main(String[] args) throws Exception {
		N = Integer.parseInt(rd.readLine());
		
		PA = new int[N + 1];
		tk = new StringTokenizer(rd.readLine());
		for (int i=1; i<=N; i++) {
			PA[i] = PA[i-1] + Integer.parseInt(tk.nextToken());
		}
		L = Integer.parseInt(rd.readLine());
		memo = new int[4][N+1];
		for (int i = N-L+1; i >= 1; i--) {
			memo[1][i] = Math.max(memo[1][i+1], PA[i+L-1] - PA[i-1]);
		}
		for (int i = N-2*L+1; i >= 1; i--) {
			memo[2][i] = Math.max(memo[2][i+1], PA[i+L-1] - PA[i-1] + memo[1][i + L]);
		}
		for (int i = N-3*L+1; i >= 1; i--) {
			memo[3][i] = Math.max(memo[3][i+1], PA[i+L-1] - PA[i-1] + memo[2][i + L]);
		}		
		
		System.out.println(memo[3][1]);
	}
}