문제 풀이

문제를 느낌을 보자마자 다이나믹 프로그래밍으로 풀어야 된다는것을 알아야한다.
dp 배열은 d[사용된 소형 기관차의 수][현재 확인하고 있는 객차 인덱스](d[j][i])로 두었다.
이 의미는 i번째 객차까지 확인하고, j개의 소형 기관차를 소모했을 때 태울 수 있는 최대 승객 수다.
즉, 예제 문제의 예제

7
35 40 50 10 30 45 60
2

에서는, d[1][2] = 2번째 객차 까지 확인 했을 때 1개의 소형 기관차를 소모했을 때 75명의 승객을 소형 기관차에 태울 수 있다.
d[1][3] = 3번째 객차 까지 확인 했을 때 1개의 소형 기관차를 소모했을때 최대값이므로 90이다.

이 패턴대로 d배열의 표를 그려보면 아래와 같다.

이 때, 일정 구간 승객들의 합을 구하기 위해서는 누적합 배열을 사용한다. (sum)

그 결과 j = (사용 소형 기관차 수), i = (현재 확인하고 있는 객차 인덱스), m = (소형 기관차가 끌 수 있는 최대 객차 수) 일때
$d[j][i] = max(d[j][i-1], d[j-1][i-m] + sum[i] - sum[i-m])$ 이라는 식이 나오게 된다.

여기서 핵심은 1, 2, 3번 객차 까지는 소형 기관차를 2개를 소비하고서는 손님을 태울 수가 없다.
마찬가지로 1, 2, 3, 4, 5번 객차 까지는 소형 기관차를 3개를 소비하고서는 손님을 태울 수가 없다.
즉, i의 시작은 j*m 부터 시작하면 된다.

문제 링크

boj/2616

소스코드

PS/2616.java

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

class Main {

  static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

  static int[] arr = new int[50010];
  static int[][] d = new int[4][50010];
  static int[] sum = new int[50010];

  public static void main(String[] args) throws Exception {

    int n = Integer.parseInt(br.readLine());
    StringTokenizer st = new StringTokenizer(br.readLine());
    for (int i = 1; i <= n; i++) {
      arr[i] = Integer.parseInt(st.nextToken());
        sum[i] = sum[i - 1] + arr[i];
    }

    int m = Integer.parseInt(br.readLine());
    for (int j = 1; j <= 3; j++) {
      for (int i = j*m; i <= n; i++) {
        d[j][i] = Math.max(d[j][i-1],d[j-1][i-m] +sum[i] - sum[i-m]);
      }

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