[문제 풀이] 백준 2616 소형기관차

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

 

 

 

처음에는 그리디로 문제인 줄 바로 코딩할까 생각하다가, 오랜만에 코테를 푸는 거라 의심하면서 조심스럽게 다시 생각해 봤습니다. 

 

"그리디 문제인가? " 에 대해서는 "매 순간 최적의 해가 정답으로 이어지는가?" 에 대해 생각을 해보면 된다는 것을 알지만 쉽지는 않죠.

 

만일 기차가 5 10 6 8 1 1 1 인 경우, 그리디로 접근하면 1번 객차에는 가장 합이 큰 10,6 객실을 선택할 것입니다. 

 

하지만 문제의 정답은 10 과 6이 동시에 선택되서는 안됩니다. 

-> 노 그리디 문제

 

브루트 포스 접근은 시간 복잡도를 어림잡아보면 안 된다는 사실을 알 수 있습니다. 

 

제가 알고있는  시간을 절약하면서 모든 경우를 확인하는 알고리즘은 이제 DP 밖에 없습니다. DP 문제를 식별하는 건 늘 소거법이 되는 것 같습니다. 

 

n번째 객실까지의 최대 승객의 수는 : 1. n번째 객실이 선택된다면 "DP(N - 객차의 길이 ) + 객차의 승객 합 " 이 되고

2. 선택되지 않는다면 DP(N-1) 이 됩니다.

 

야호!

 

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

public class Num2616_소형기관차 {
    static int n, l;
    static int[] arr;
    static int[][] memo;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        arr = new int[n+1];
        memo = new int[n+1][4];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=1;i<=n;i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }
        l = Integer.parseInt(br.readLine());
        System.out.println(dp(n, 3));
//        for (int i= 1; i<= n;i++){
//            System.out.println(Arrays.toString(memo[i]));
//        }
    }
    public static int dp(int index, int cnt){
        if(memo[index][cnt] != 0) return memo[index][cnt];
        if(index < l || cnt == 0) return memo[index][cnt];
        int tmp = 0;
        int sum = 0;
        while ( tmp < l){
            sum += arr[index - tmp];
            tmp ++;
        }
         return memo[index][cnt] = Math.max(dp(index-1,cnt) , dp(index-l,cnt-1) + sum);
    }
}