[백준 2096] 내려가기 / 자바 / dp + 슬라이딩 윈도우

문제         

레벨: G5
알고리즘: dp + 슬라이딩 윈도우 
풀이시간: 1시간
힌트 참조 유무: 유 

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

1 번째 시도   

[알고리즘 설명]

위 방식을 어떻게 dp 로 구현하지? 
아무리 생각해도 작은 문제를 해결해서 위 문제를 해결하지 못할 것 같은데 ?
1줄만 있는 경우  -> 2줄만 있는 경우 - > 3줄만 있는 경우 이런 식으로 업데이트 해도 조건이 달라질 때마다 경로가 달라지는데?

=> dp[]의 각 원소를 각 줄의 최적값으로 생각하지 말고, 한 줄의 세 숫자의 최적값으로 생각하자.

위 고민들을 dp[] size = 3배열로 해결할 수 있다. 나는 최소, 최댓값을 구하기 위한 경로에 집착했다. 관점을 달리해 매줄 마다 세 개의 숫자에 지난 줄에서 선택할 수 있는 최소, 최대값을 더해서 업데이트 해주면 되는 것이다. 

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        
        int[][] maxDp = new int[2][3];
        int[][] minDp = new int[2][3];
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int j = 0; j < 3; j++) {
            int num = Integer.parseInt(st.nextToken());
            maxDp[0][j] = minDp[0][j] = num;
        }
        
        for (int i = 1; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            
            // Max DP
            maxDp[1][0] = Math.max(maxDp[0][0], maxDp[0][1]) + a;
            maxDp[1][1] = Math.max(Math.max(maxDp[0][0], maxDp[0][1]), maxDp[0][2]) + b;
            maxDp[1][2] = Math.max(maxDp[0][1], maxDp[0][2]) + c;
            
            // Min DP
            minDp[1][0] = Math.min(minDp[0][0], minDp[0][1]) + a;
            minDp[1][1] = Math.min(Math.min(minDp[0][0], minDp[0][1]), minDp[0][2]) + b;
            minDp[1][2] = Math.min(minDp[0][1], minDp[0][2]) + c;
            
            for (int j = 0; j < 3; j++) {
                maxDp[0][j] = maxDp[1][j];
                minDp[0][j] = minDp[1][j];
            }
        }
        
        int maxResult = Math.max(Math.max(maxDp[0][0], maxDp[0][1]), maxDp[0][2]);
        int minResult = Math.min(Math.min(minDp[0][0], minDp[0][1]), minDp[0][2]);
        
        System.out.println(maxResult + " " + minResult);
    }
}