bj2096(내려가기)-dp

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

 

메모리가 4MB이다.

빡세다. 이런 문제는 풀지 말자. 코테에 안나온다.

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

public class Main {
    static int N;
    static int[] max_dp;
    static int[] min_dp;
    static StringTokenizer stringTokenizer;
    static BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        initialize();
        int[] answers = solve();
        System.out.println(answers[0] + " " + answers[1]);
    }

    private static void initialize() throws IOException {
        N = Integer.parseInt(bufferedReader.readLine());
        max_dp = new int[3];
        min_dp = new int[3];

        stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        for (int x = 0; x < 3; x++) {
            int num = Integer.parseInt(stringTokenizer.nextToken());
            max_dp[x] = num;
            min_dp[x] = num;
        }
    }

    private static int[] solve() throws IOException {
        for (int y = 1; y < N; y++) {
            int[] currMax = new int[3];
            int[] currMin = new int[3];
            for (int x = 0; x < 3; x++) {
                currMax[x] = Integer.MIN_VALUE;
                currMin[x] = Integer.MAX_VALUE;
            }

            if(N != 1){
                stringTokenizer = new StringTokenizer(bufferedReader.readLine());
                int[] row = new int[3];
                for (int x = 0; x < 3; x++) {
                    row[x] = Integer.parseInt(stringTokenizer.nextToken());
                }
                for (int x = 0; x < 3; x++) {
                    for (int i = -1; i <= 1; i++) {
                        int nx = x + i;
                        if (nx < 0 || nx >= 3) continue;
                        currMax[x] = Math.max(currMax[x], max_dp[nx] + row[x]);
                        currMin[x] = Math.min(currMin[x], min_dp[nx] + row[x]);
                    }
                }
                max_dp = currMax;
                min_dp = currMin;
            }
        }

        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        for (int x = 0; x < 3; x++) {
            max = Math.max(max, max_dp[x]);
            min = Math.min(min, min_dp[x]);
        }
        return new int[]{max, min};
    }
}