[백준 2616번/Java] 소형기관차

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

 

[문제 분석]

 길이 N의 수열을 M개씩 3개로 묶을 때 최댓값을 구하는 문제이다.

[알고리즘]

1. 연속된 수열을 가져와야하기 때문에 누적합을 사용하여 시간을 단축한다.

2. 이 문제는 결국 모든 경우의 수를 살펴봐야하는데 그것을 얼마나 효율적으로 메모이제이션하느냐에 따라 달려있다.

 

DP[i][j] = i번 열차가 j번 수열까지 도달했을 때 최대 값

 

이 점화식은 배낭문제에서 아이디어를 가져올 수 있다. 다만 배낭문제는 각 배낭에 각 객체를 넣을 수 있을지 없을지 확인하는데 이것은 연속된 객체를 삽입할지 말지 결정해야하는 다른점이 있다. 

 

그렇다면 점화식은 어떻게 구성해야할까 먼저 예제로 시뮬레이션 해보자.

 

N = 7, M = 2

35 40 50 10 30 45 60 

 

먼저 누적합을 구한다.

0	1	2	3	4	5	6	7
0	35	75	125	135	165	210	270

 

첫번째 기관차를 가정하자.

1번 객실부터 살펴볼 것이다. 2번객실까지 확인했을 때 객실이 2개(M개)이므로 끌 수 있다.

 

그리고 3번객실을 살펴보았을 때

1. [1,2]번 객실을 그대로 갖고 있을 수 있다.

2. [2,3]번 객실로 갱신 할 수 있다.

 

아하.. 그렇다면 점화식을 새울 수 있겠다.

 

DP[i][j] = MAX ( DP[i][j - 1], prefix[j] - prefix[j - M])

 

하지만 이렇게하면 열차가 하나이면 모를까 2개 이상이되면 성립하지 않는다. 2번에서 이전 열차까지 고려를 해주어야한다. 이는 배낭문제에서 이전타겟까지만 바라보고 있을 때를 고려해주는 것과 같은 맥락이다.

 

현재 j - M 번, 예를들어 2번열차,  j = 6, M = 2 라고 할 때 1번열차의 j = 4까지(j - M)의 최댓값을 고려해야한다는 것이다.

 

그래서 최종 점화식은 다음과 같다.

 

DP[i][j] = MAX ( DP[i][j - 1], DP[i - 1][j - M] + prefix[j] - prefix[j - M])

 

이 문제는 누적합과 동적계획법이 결합한 문제다. 처음에는 선택되지 않은 부분을 최소화하는 방식을 해답이라 생각하였으나 어떻게 구현해야할지 감이 잡히지 않았다. 결국 잘못된 방법임을 알게되었고 배낭문제를 떠올려 문제를 풀 수 있었다. 사실 이런 문제도 풀어본적이 있어야 맞출 수 있는 문제인 것 같다. 매우 좋은 문제!

 

갱신조건과 입출력을 더한 최종 코드는 다음과 같다. 

 

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

class Main {
    static int MAX = 50001;
    static int[] prefix = new int[MAX];
    static int[][] dp = new int[4][MAX];

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] input = br.readLine().split(" ");
        int N = Integer.parseInt(input[0]);

        ArrayList<Integer> arr = new ArrayList<>();

        input = br.readLine().split(" ");
        for(String s : input){
            arr.add(Integer.parseInt(s));
        }

        for(int i = 1; i <= arr.size(); i++){
            prefix[i] += (prefix[i - 1] + arr.get(i - 1));
        }

        input = br.readLine().split(" ");

        int M = Integer.parseInt(input[0]);

        for(int i = 1; i < 4; i++){
            for(int j = 0; j <= N; j++){
                if(j >= M){
                    dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j - M] + (prefix[j] - prefix[j - M]));
                }else{
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }

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