[BOJ 2616] 소형기관차(Java, Dynamic Programming, 동적계획법, Bottom-up, Top-down 풀이)

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

2616번: 소형기관차

1. 다이나믹 프로그래밍 정의에 맞게 작은 문제를 이용해 큰 문제를 해결하기 위해 두 가지 매개변수 이용(소형기관차의 수, 탐색한 객실 번호) 

 * 다이나믹 프로그래밍 감이 오지 않는다면, https://www.zerocho.com/category/Algorithm/post/584b979a580277001862f182 참고

 

 

 

2. 2차원 형태의 배열을 생각하고 점화식을 고려(행 : 소형기관차의 수, 열 : 검사한 객실 번호들 중 가장 큰 수) 

* R = 행, C = 열, K = 소형기관차 최대로 끌 수 있는 객차 수

* DP[R][C] = max(DP[R][C - 1], DP[R - 1][C - K] + (SUM[C] - SUM[C - K])

 

 

---

해설코드(Java, Bottom-up). 

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Main
{
    public static void main (String[] args) throws java.lang.Exception
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int N = Integer.valueOf(br.readLine());
        String[] sArr = br.readLine().split(" ");
        int M = Integer.valueOf(br.readLine());
        
        int[] sumArr = new int[N + 1];
        int answer = 0;
        
        sumArr[0] = 0;
        for(int i = 0; i < N; i++){
            sumArr[i + 1] = sumArr[i] + Integer.valueOf(sArr[i]);
        }
        
        int[][] dp = new int[4][N + 1];
        for(int i = 1; i <= 3; i++){
            for(int j = 1; j <= N; j++){
                dp[i][j] = 0;
                if(j - M >= 0){
                    dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j - M] + (sumArr[j] - sumArr[j - M]));
                }
                answer = Math.max(dp[i][j], answer);
            }
        }
        
        bw.write(answer + "\n");
        bw.flush();
    }
}

 

해설코드(Java, Top-Down). 

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Main
{
    static int N, M;
    static int[][] dp;
    static int[] sumArr;
 
    public static void main (String[] args) throws java.lang.Exception
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        N = Integer.valueOf(br.readLine());
        String[] sArr = br.readLine().split(" ");
        M = Integer.valueOf(br.readLine());
        
        sumArr = new int[N + 1];
        
        sumArr[0] = 0;
        for(int i = 0; i < N; i++){
            sumArr[i + 1] = sumArr[i] + Integer.valueOf(sArr[i]);
        }
        
        dp = new int[4][N + 1];
        for(int i = 1; i < dp.length; i++){
            for(int j = 1; j < dp[i].length; j++){
                dp[i][j] = -1;
            }
        }
 
        bw.write(func(3, N) + "\n");
        bw.flush();
    }
    
    public static int func(int R, int C){
        if(R == 0 || C == 0)
            return 0;
             
        if(dp[R][C] != -1)
            return dp[R][C];
        
        dp[R][C] = 0;
        if(C - M >= 0){
            dp[R][C] = Math.max(func(R, C - 1), func(R - 1, C - M) + sumArr[C] - sumArr[C - M]);
        }
        
        return dp[R][C];
    }
}