백준 - 내려가기

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[] maxdp = new int[3];
        int[] mindp = new int[3];
        int[] current = new int[3];
        int[] temp = new int[3];


        StringTokenizer st = new StringTokenizer(br.readLine());
        maxdp[0] = mindp[0] = Integer.parseInt(st.nextToken());
        maxdp[1] = mindp[1] = Integer.parseInt(st.nextToken());
        maxdp[2] = mindp[2] = Integer.parseInt(st.nextToken());

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


            temp[0] = current[0] + Math.max(maxdp[1], maxdp[0]);
            temp[1] = current[1] + Math.max(maxdp[1], Math.max(maxdp[0], maxdp[2]));
            temp[2] = current[2] + Math.max(maxdp[1], maxdp[2]);
            maxdp[0] = temp[0];
            maxdp[1] = temp[1];
            maxdp[2] = temp[2];


            temp[0] = current[0] + Math.min(mindp[0], mindp[1]);
            temp[1] = current[1] + Math.min(mindp[1], Math.min(mindp[0], mindp[2]));
            temp[2] = current[2] + Math.min(mindp[1], mindp[2]);
            mindp[0] = temp[0];
            mindp[1] = temp[1];
            mindp[2] = temp[2];

        }

        System.out.println(Math.max(maxdp[0], Math.max(maxdp[1], maxdp[2])));
        System.out.println(Math.min(mindp[0], Math.min(mindp[1], mindp[2])));

    }
}

dp관련 문제입니다.
dp[i][j]의 경우 dp[i-1][j-1],dp[i-1][j],dp[i-1][j+1]의 값 중 가장 큰 값을 더해주면 되고 최소값의 경우에는 가장 작은 값을 넣어주면 됩니다. 위 코드의 경우에는 배열을 N만큼 만들어주는 방법이 아닌 제자리를 이용한 방식이라고 이해하시면 될 것 같습니다.

주의 : java 버전을 15로 할 경우 계속 메모리 초과가 발생합니다. -> 자바 11로 낮춰서 해보시면 될 것 같습니다.(이 것 때문에 시간이 많이 걸렸습니다....)

출처 : 백준 - 내려가기