[백준] no2096:내려가기 - 슬라이딩 윈도우 기법 DP

문제

Input

1. N * 3의 사이즈로 임의의 숫자로 된 맵이 주어진다.
2. 이동은 현재 위치의 다음줄에서 양옆 한칸씩(즉 바로아래와 대각선 방향)인 곳만 이동이 가능하다.

Output

첫 줄에서 끝줄로 가는 경우 중, 가장 비용이 큰 경우와 적은 경우를 구해라.

---

원리 - 슬라이딩 윈도우 기법

사용 이유 : 메모리 제한이 있으므로, 기존의 모든값 저장방식의 DP로는 메모리 초과가 발생한다.

원리 :

             * 1. maxDP에는 항상 합산의 최대값들로 저장 && minDP에는 항상 합산의 최소값들로 저장되도록 할 것이다.
             * 2. 따라서 새 줄을 입력받을 때, 이전 최대값 중 양쪽 끝값을 임시 저장한다.
             * 3. 0번째는 결국 이전 0번째와 1번째 중 하나와 현재 값의 합산이 될 것이다.
             * 4. 2번째는 결국 이전 1번째와 2번째 중 하나와 현재 값의 합산이 될 것이다.
             * 5. 1번째는 결국 이전 0번째와 1번째를 비교한 뒤 -> 둘중 더 큰(작은)값과 2번째 값을 비교해서 큰(작은)값이 들어간다.
             * 6. 이 과정을 N번쨰 줄까지 반복한다.

핵심 코드 :

            // max값 구하기
            int beforeMax_0 = maxDP[0];
            int beforeMax_2 = maxDP[2];
            maxDP[0] = Math.max(beforeMax_0, maxDP[1]) + A;
            maxDP[2] = Math.max(beforeMax_2, maxDP[1]) + C;
            maxDP[1] = Math.max(Math.max(beforeMax_0, maxDP[1]), beforeMax_2) + B;

            // min값 구하기
            int beforeMin_0 = minDP[0];
            int beforeMin_2 = minDP[2];
            minDP[0] = Math.min(beforeMin_0, minDP[1]) + A;
            minDP[2] = Math.min(beforeMin_2, minDP[1]) + C;
            minDP[1] = Math.min(Math.min(beforeMin_0, minDP[1]), beforeMin_2) + B;

---

나의 코드

[메모리초과] DP를 이용한 모든 경우 구하기

: 입력값을 모두 받아서 DP로 해결하려 했으나, 메모리 제한이 4MB밖에 되지 않기 때문에 최대길이 100000을 감당할 수 없다.

private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    private static int N;
    private static int[][] map;
    private static Integer[][] dp;
    private static int[] move = {-1, 0, 1};

    public static void main(String[] args) throws IOException {

        N = Integer.parseInt(br.readLine());
        map = new int[N][N];

        for(int i = 0; i< N ; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            for(int j = 0; j< 3 ; j++) map[i][j] = Integer.parseInt(st.nextToken());
        }

        bw.append(""+maxValue()).append(" ").append(""+minValue());

        bw.close();
    }

    private static int maxValue() {
        dp = new Integer[N][N];

        for(int i = 0; i< 3 ; i++) dp[0][i] = map[0][i];

        for(int i = 0; i< N-1 ; i++) {
            for(int j = 0; j<3 ; j++) {
                for (int k = 0; k < 3; k++) {
                    if (move[k] + j < 0 || move[k] + j > 2) continue;

                    int next = move[k] + j;
                    if(dp[i + 1][next] == null) {
                        dp[i + 1][next] = dp[i][j] + map[i+1][next];
                        continue;
                    }
                    dp[i + 1][next] = Math.max(dp[i + 1][next], dp[i][j] + map[i+1][next]);
                }
            }
        }

        int max= 0;
        for(int i = 0; i<3 ; i++) max = Math.max(dp[N-1][i], max);
        return max;
    }

    private static int minValue() {
        dp = new Integer[N][N];
        for(int i = 0; i< 3 ; i++) dp[0][i] = map[0][i];

        for(int i = 0; i< N-1 ; i++) {
            for(int j = 0; j<3 ; j++) {
                for (int k = 0; k < 3; k++) {
                    if (move[k] + j < 0 || move[k] + j > 2) continue;

                    int next = move[k] + j;
                    if(dp[i + 1][next] == null) {
                        dp[i + 1][next] = dp[i][j] + map[i+1][next];
                        continue;
                    }
                    dp[i + 1][next] = Math.min(dp[i + 1][next], dp[i][j] + map[i+1][next]);
                }
            }
        }

        int min= Integer.MAX_VALUE;
        for(int i = 0; i<3 ; i++) min = Math.min(dp[N-1][i], min);
        return min;
    }

 

[성공] 슬라이딩 윈도우 DP 방식

: 반복이 적기때문에 시간복잡도가 낮아지고, 일차원 배열 2개로만 사용하기 때문에 메모리 소모도 적다.

    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    public static void main(String[] args) throws IOException {
        int N = Integer.parseInt(br.readLine());
        int[] maxDP = new int[3];
        int[] minDP = new int[3];
        StringTokenizer st;

        OUTER : for(int i=0 ; 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());

            // 첫 번째 줄은 무조건 들어가야함
            if(i==0) {
                maxDP[0] = minDP[0] = A;
                maxDP[1] = minDP[1] = B;
                maxDP[2] = minDP[2] = C;
                continue OUTER;
            }

            /**
             * 원리
             * 1. maxDP에는 항상 합산의 최대값들로 저장 && minDP에는 항상 합산의 최소값들로 저장되도록 할 것이다.
             * 2. 따라서 새 줄을 입력받을 때, 이전 최대값 중 양쪽 끝값을 임시 저장한다.
             * 3. 0번째는 결국 이전 0번째와 1번째 중 하나와 현재 값의 합산이 될 것이다.
             * 4. 2번째는 결국 이전 1번째와 2번째 중 하나와 현재 값의 합산이 될 것이다.
             * 5. 1번째는 결국 이전 0번째와 1번째를 비교한 뒤 -> 둘중 더 큰(작은)값과 2번째 값을 비교해서 큰(작은)값이 들어간다.
             * 6. 이 과정을 N번쨰 줄까지 반복한다.
             */

            // max값 구하기
            int beforeMax_0 = maxDP[0];
            int beforeMax_2 = maxDP[2];
            maxDP[0] = Math.max(beforeMax_0, maxDP[1]) + A;
            maxDP[2] = Math.max(beforeMax_2, maxDP[1]) + C;
            maxDP[1] = Math.max(Math.max(beforeMax_0, maxDP[1]), beforeMax_2) + B;

            // min값 구하기
            int beforeMin_0 = minDP[0];
            int beforeMin_2 = minDP[2];
            minDP[0] = Math.min(beforeMin_0, minDP[1]) + A;
            minDP[2] = Math.min(beforeMin_2, minDP[1]) + C;
            minDP[1] = Math.min(Math.min(beforeMin_0, minDP[1]), beforeMin_2) + B;
        }
        bw.write("" + Math.max(Math.max(maxDP[0],maxDP[1]), maxDP[2]) + " ");
        bw.write(""+ Math.min(Math.min(minDP[0],minDP[1]), minDP[2]));

        bw.close();
    }

---

레퍼런스

참고 링크 : https://steady-coding.tistory.com/154