문제

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

Gold V

코드 (Java)

import java.util.Scanner;

public class Main {
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = Integer.parseInt(sc.nextLine());
        int [] board = new int[3];
        int [] container = new int[3];
        int [] max_dp = new int[3];
        int [] min_dp = new int[3];

        for (int i = 0; i < N; ++i) {
            board[0] = sc.nextInt();
            board[1] = sc.nextInt();
            board[2] = sc.nextInt();
            sc.nextLine();

            if (i == 0) {
                max_dp[0] = board[0];
                max_dp[1] = board[1];
                max_dp[2] = board[2];
                min_dp[0] = board[0];
                min_dp[1] = board[1];
                min_dp[2] = board[2];
                continue;
            }

            //left max
            container[0] = Integer.max(max_dp[0], max_dp[1]) + board[0];
            //center max
            container[1] = Integer.max(Integer.max(max_dp[0], max_dp[1]), max_dp[2]) + board[1];
            //right max
            container[2] = Integer.max(max_dp[1], max_dp[2]) + board[2];

            max_dp[0] = container[0];
            max_dp[1] = container[1];
            max_dp[2] = container[2];

            //left min
            container[0] = Integer.min(min_dp[0], min_dp[1]) + board[0];
            //center max
            container[1] = Integer.min(Integer.min(min_dp[0], min_dp[1]), min_dp[2]) + board[1];
            //right max
            container[2] = Integer.min(min_dp[1], min_dp[2]) + board[2];

            min_dp[0] = container[0];
            min_dp[1] = container[1];
            min_dp[2] = container[2];
        }

        int max = Integer.max(Integer.max(max_dp[0], max_dp[1]), max_dp[2]);
        int min = Integer.min(Integer.min(min_dp[0], min_dp[1]), min_dp[2]);

        System.out.printf("%d %d", max, min);
    }
}

풀이

문제도, 구현도 어렵지는 않다. 조금 메모리가 빡빡한 DP로 코드를 보면 직관적으로 이해는 될것이다.

문제는 Java15로 문제를 풀려고 하면 항상 메모리 초과가 난다.(...) 위 코드도 Java15로는 메모리 초과가 나나 Java11로 하면 잘 된다...