슬라이딩 윈도우

온라인 알고리즘 : Stream처럼 들어오는 데이터 모두 저장하는 것이 아닌 들어오는 대로 바로바로 처리하는 알고리즘.

슬라이딩 위도우도 이 중 하나!
창문으로 보이는 부분 만큼만 저장하는 것.
어디서 들어봤나 생각했는데 운영체제에서 들어본 것이었음.
-> 슬라이딩 위도우 프로토콜 (Go back N, 선택적 재전송 등등,,)

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

일반 dp를 사용해 이차원 배열을 사용하면 메모리 초과가 나온다.
-> 슬라이딩 윈도우를 사용해 위, 아래 두줄만 창문으로 바라보면 되는 문제.
3칸으로 고정되어 있기 때문.

/*
슬라이딩 원도우
현재위치 map[y][x]
가능위치 map[y-1][x+1], map[y][x+1], map[y+1][x+1]

최대값, 최소값
 */
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[] dpMax = new int[3];
        int[] dpMin = new int[3];

        StringTokenizer st;
        for (int i=0; i<n; i++) {
            st = new StringTokenizer(br.readLine());

            int x1 = Integer.parseInt(st.nextToken());
            int x2 = Integer.parseInt(st.nextToken());
            int x3 = Integer.parseInt(st.nextToken());

            // 첫 줄
            if (i == 0) {
                dpMax[0] = dpMin[0] = x1;
                dpMax[1] = dpMin[1] = x2;
                dpMax[2] = dpMin[2] = x3;
            } else {
                int beforeMax = dpMax[0];
                int afterMax = dpMax[2];
                dpMax[0] = Math.max(dpMax[0], dpMax[1]) + x1;
                // 순서
                dpMax[2] = Math.max(dpMax[1], dpMax[2]) + x3;
                dpMax[1] = Math.max(Math.max(beforeMax, dpMax[1]), afterMax) + x2;

                int beforeMin = dpMin[0];
                int afterMin = dpMin[2];
                dpMin[0] = Math.min(dpMin[0], dpMin[1]) + x1;
                dpMin[2] = Math.min(dpMin[1], dpMin[2]) + x3;
                dpMin[1] = Math.min(Math.min(beforeMin, dpMin[1]), afterMin) + x2;
            }
        }

        int max = Math.max(dpMax[0], Math.max(dpMax[1], dpMax[2]));
        int min = Math.min(dpMin[0], Math.min(dpMin[1], dpMin[2]));

        System.out.print(max + " " + min);
    }
}

[참고]
https://steady-coding.tistory.com/154
https://www.youtube.com/watch?v=ySECi-s5fQY