[백준 2616] 소형기관차

문제

https://www.acmicpc.net/problem/2616

2616번: 소형기관차

 

 

풀이

문제는 크게 dp를 사용해 풀이한다. 하지만 누적합의 개념도 적용된다.

누적합

문제를 풀기 위해선 누적합을 통해 점화식을 작성해야 한다.

누적합이란 Prefix Sum이라 불린다. 말 그대로 해당 구간에 대해 누적된 합을 구하는 알고리즘이다. 배열의 값이 바뀌지 않는다는 조건이 있을 때 적용이 가능하다.

 

자신의 인덱스 값과 이전 인덱스 값을 더하며 구현한다. 예를들어 [1, 3, 5]이란 배열이 존재한다고 했을 때, 누적합을 구하는 sum배열의 3번째 요소의 값은 4와 5를 더한 9이다. 이전의 요소가 4인 것은 1과 3의 누적된 합이기 때문에 3번째 요소의 값을 구할 때 적용이 가능한 것이다.

 

이 개념을 적용해 객차가 태운 손님의 누적합을 구한다.

 

DP

점화식을 통해 객차의 손님들의 최대로 이송할 수 있는 누적 값을 dp에 저장해야 한다. 소형기관차가 max만큼의 객차를 운반할 수 있으므로, 객차 구간 만큼 승객 수를 저장한다. 이렇게 저장이 됐다면 dp[1]에는 첫번째 소형기관차가 운반할 수 있는 구간별 최대 승객의 수가 저장되었을 것이다. 따라서 dp[3]의 마지막 요소에는 운반할 수 있는 최대 승객 수가 저장되는 것이다.

 

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

 

위 코드는 현재 인덱스 이전의 값과, 이전 소형기관차가 운반한 객차 + 현재의 소형기관차가 운반할 객차 값을 비교해서 더 큰 값을 저장한다.

 

코드

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[] sum = new int[n + 1];

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

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

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