백준 2096 번 : 내려가기 풀이 (Java)

www.acmicpc.net/problem/2096

2096번: 내려가기

문제를 잘 읽자.

Solution

1. 이 문제의 해법 자체는 dp 문제를 조금이라도 풀어봤다면 어렵지 않을 것이다. dp[i][j] 는, dp[i-1][j-1], dp[i-1][j], dp[i-1][j+1] 중에 최대값, 최소값을 가져와서 입력받았던 input[i][j] 를 더해주면 될 것이다.

2. 하지만 이 문제는 메모리 제한이 있다. 나는 얼마나 줄여야 메모리 초과가 안날지 궁금해서 가장 처음 떠오르는 방법부터 차근차근 해봤었다. 그리고 나는 이 문제의 행이 3개로 고정 되어있다는 걸 나중에 알았다.(문제 잘읽자 제발!!!) 아래에 적는 것 중에 열 부분의 N을 3이라 생각하고 봐주시길 바란다. (런타임 에러 이유 표시가 안됐다면 지옥이지 않았을까)

- N*N*2 (2는 최대, 최소를 한 배열에서 해결하기 위해) 의 dp 배열 + N*N의 map 배열  -> 바로 초과

- N*N 의 dp배열 2개 + N*N의 map 배열 -> 초과

- N*N의 dp 배열 2개 -> 초과

- 2*N의 dp 배열 2개 -> 초과안남

 

즉, 우리가 선택할 것은 2*3 의 dp 배열 2개이다. 왜 2*3 만으로 되는 걸까? 그 이유는,

지금 행과 이전 행 만 비교하면 되기 때문이다.

굳이 필요없는 행들 까지 다 저장할 필요가 아예 없다는 것이다.

그러므로 해법은 이렇게 될 것이다.

1. 입력을 받으면서 dp[0][j-1], dp[0][j], dp[0][j+1] 중에 최대값, 최소값 + 입력값 을 dp[1][j] 에 저장해준다. 입력을 받으면서 해야 N*3의 배열을 쓸 필요가 없어진다.

2. 모든 열의 값이 계산됐다면, dp[1] 배열을 dp[0] 에 deepcopy 해주고, dp[1] 배열은 0으로 모두 초기화해준다. 행을 올려주는 것이다.

3. 1, 2 를 반복한다.

 

Source Code

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bufferedWriter = new BufferedWriter(new OutputStreamWriter(System.out));
    static int N, max = Integer.MIN_VALUE, min = Integer.MAX_VALUE;
    static int[][] dp1, dp2;
    static void input() throws IOException {
        N = Integer.parseInt(bufferedReader.readLine());
        dp1 = new int[2][3];
        dp2 = new int[2][3];
        for(int i = 0 ; i < N; i++) {
            StringTokenizer st = new StringTokenizer(bufferedReader.readLine());
            for(int j = 0; j < 3; j++) {
                dp1[1][j] = Integer.parseInt(st.nextToken());
                dp2[1][j] = dp1[1][j];
                if(j == 0) {
                    dp1[1][j] = Math.max(dp1[0][0], dp1[0][1]) + dp1[1][0];
                    dp2[1][j] = Math.min(dp2[0][0], dp2[0][1]) + dp2[1][0];
                } else if(j == 2) {
                    dp1[1][j] = Math.max(dp1[0][2], dp1[0][1]) + dp1[1][2];
                    dp2[1][j] = Math.min(dp2[0][2], dp2[0][1]) + dp2[1][2];
                } else {
                    dp1[1][1] = Math.max(Math.max(dp1[0][0], dp1[0][1]), dp1[0][2]) + dp1[1][1];
                    dp2[1][1] = Math.min(Math.min(dp2[0][0], dp2[0][1]), dp2[0][2]) + dp2[1][1];
                }
            }
            dp1[0] = dp1[1].clone();
            dp2[0] = dp2[1].clone();
            Arrays.fill(dp1[1], 0);
            Arrays.fill(dp2[1], 0);
        }
        for(int j = 0 ; j < 3; j++) {
            max = Math.max(max, dp1[0][j]);
            min = Math.min(min, dp2[0][j]);
        }
        bufferedWriter.write(max + " " + min);
    }


    public static void main(String[] args) throws IOException {
        input();
        bufferedReader.close();
        bufferedWriter.close();
    }
}