[백준] 2616 소형기관차 - DP, 누적합

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

🍊해결방법

• i번째에서 M개까지 기차를 끌고 간다 -> 다음으로는 i+M번째로
• i번째에서 선택을 하지 않는다
• train(idx+M, cnt+1) / train(idx+1, cnt) 두 경우의 수 중 최대값을 return 한다
• 최대값을 계산할 때 누적합을 활용하자 prefix[idx+M-1] - prefix[idx-1]
• 중복된 계산을 할 수 있으므로 dp에 저장하자

😀풀이

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

public class Main {

    static int N;
    static int[] arr;
    static int[] prefix;
    static int M;
    static int[][] dp;


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

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

        // 소형기관차 최대로 끌 수 있는 객차의 수는 같다, 넘기면 안됨, 최대한 많은 손님
        // 번호가 연속적으로 이어지도록 3 5 이런건 안됨
        // 각 구간을 구하고 그 구간을 각각 더하는 것을 누적합 활용
        // 중복되는 계산값은 dp에 저장

        N = Integer.parseInt(br.readLine());

        arr = new int[N+1];

        StringTokenizer st = new StringTokenizer(br.readLine());

        for(int i=1; i<=N; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }

        // 누적합
        prefix = new int[N+1];

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

        // 객차 수
        M = Integer.parseInt(br.readLine());

        dp = new int[N+1][4];

        for(int i=1; i<=N; i++){
            Arrays.fill(dp[i], -1);
        }

        int ans = train(1, 0);


        System.out.println(ans);


    }


    static int train(int idx, int cnt){

        if (cnt == 3) return 0;

        if (idx > N) return 0;

        if (dp[idx][cnt] != -1) return dp[idx][cnt];

        int tmp = 0;

        // M칸만큼 선택
        if (idx+M-1 <= N)
            tmp = Math.max(tmp, train(idx+M, cnt+1) + (prefix[idx+M-1] - prefix[idx-1]));

        // 선택안하고 다음거
        tmp = Math.max(tmp, train(idx+1, cnt));

        dp[idx][cnt] = tmp;

        return dp[idx][cnt];
    }

}