[백준] 2096 내려가기 [java]

문제

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

풀이 방법

위 그림의 규칙으로 밑으로 내려가면서 최소 , 최대 비용을 저장하는 것인데,
BFS + dp로 풀면 메모리 초과가 난다.
따라서, 슬라이딩 윈도우로 풀었다.
현재까지의 최대, 최소를 저장하는 배열을 두개 선언하고 그 배열을 밑으로 내리면서 값을 갱신한다고 생각하면 된다.

소스 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(bufferedReader.readLine());

        int[] maxDp = new int[3];
        int[] minDp = new int[3];
        for(int i = 0; i < n; i++){
            StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
            int num0 = Integer.parseInt(stringTokenizer.nextToken());
            int num1 = Integer.parseInt(stringTokenizer.nextToken());
            int num2 = Integer.parseInt(stringTokenizer.nextToken());

            if(i == 0){
                maxDp[0] = minDp[0] = num0;
                maxDp[1] = minDp[1] = num1;
                maxDp[2] = minDp[2] = num2;
            }
            else{
                int prevMaxDp0 = maxDp[0], prevMaxDp1 = maxDp[1], prevMaxDp2 = maxDp[2];
                maxDp[0] = Math.max(prevMaxDp0, prevMaxDp1) + num0;
                maxDp[1] = Math.max(prevMaxDp0, Math.max(prevMaxDp1, prevMaxDp2)) + num1;
                maxDp[2] = Math.max(prevMaxDp1, prevMaxDp2) + num2;

                int prevMinDp0 = minDp[0], prevMinDp1 = minDp[1], prevMinDp2 = minDp[2];
                minDp[0] = Math.min(prevMinDp0, prevMinDp1) + num0;
                minDp[1] = Math.min(prevMinDp0, Math.min(prevMinDp1, prevMinDp2)) + num1;
                minDp[2] = Math.min(prevMinDp1, prevMinDp2) + num2;
            }
        }

        Arrays.sort(maxDp);
        Arrays.sort(minDp);

        System.out.println(maxDp[2] + " " + minDp[0]);
    }
}