boj 2616 소형기관차

www.acmicpc.net/problem/2616

2616번: 소형기관차

객차에 타고있는 손님의 수가 주어지고, 소형기관차가 최대로 끌 수 있는 객차의 수가 주어집니다.

 

저의 솔루션입니다.

dp[idx][cnt] : idx의 위치에서 cnt번째 소형기관차에서 끌 수 있는 최대 손님 수

 

객차에 타고있는 손님의 수를 누적합으로 미리 계산합니다.

func함수에서 가지치기 해야할 것

1. 현재 idx부터 모든 객차를 고를 수 없는 경우

(ex) N = 7, M = 2이고 첫번째 기관차인데 idx가 3인 경우 => 3 - 1 + M * 3 > N)

2. 이미 3개모두 골랐을 경우 (cnt == 0)

 

dp[idx][cnt] != -1 이면 값이 구해진 상태이므로 dp[idx][cnt]를 바로 리턴합니다.

dp[idx][cnt] 값은 현재idx를 고르는 경우와 안고르고 다음idx로 넘겨주는 경우의 최댓값을 구해주시면 됩니다.

현재idx를 고르는 경우에는 구해놨던 누적합을 이용하여 합을 더해주고 func(idx + M, cnt - 1)을 호출

안고르는 경우에는 바로 func(idx + 1, cnt)를 호출해주시면 됩니다.

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int list[] = new int[50001];
    static int dp[][] = new int[50001][4];
    static int N, M;
 
    static void init() {
        for (int i = 1; i <= N; i++)
            Arrays.fill(dp[i], -1);
    }
 
    static int func(int idx, int cnt) {
        if (idx + M * cnt - 1 > N)
            return 0;
        if (cnt == 0)
            return 0;
 
        if (dp[idx][cnt] != -1)
            return dp[idx][cnt];
 
        dp[idx][cnt] = 0;
 
        dp[idx][cnt] = Math.max(func(idx + 1, cnt), func(idx + M, cnt - 1) + list[idx + M - 1] - list[idx - 1]);
 
        return dp[idx][cnt];
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        init();
 
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            list[i] = Integer.parseInt(st.nextToken());
            list[i] += list[i - 1];
        }
        st = new StringTokenizer(br.readLine());
        M = Integer.parseInt(st.nextToken());
    }
 
    public static void main(String[] args) throws Exception {
        input();
        System.out.println(func(1, 3));
    }
}