문제 풀이

탑 다운 dp 연습 겸 탑 다운 방식으로 풀이했다.
최대 값, 최소 값을 모두 구해야 하므로 두 개의 dp배열, 최대 값을 구하는 함수, 최소 값을 구하는 함수 두가지를 작성했다.

d배열은 최대 값을 저장하는 배열, d2배열은 최소 값을 저장할 배열이다.
최대 최소를 저장해야하므로 각각 -1, 987654321로 초기화 시켜주었다.

기저 사례로 i == n-1일 경우 arr[i][j]를 반환해 준다.
그 외에는 현재의 최대 또는 최소값 = 현재 위치한 배열의 값 + 그 다음 줄에서 얻을 점수의 최대 값 또는 최소 값이라고 생각하면
d[0][0], d[0][1], d[0][2] 중에서 최대값을 얻어낼 수 있고
d2[0][0], d2[0][1], d[0][2] 중에서 최소 값을 얻어낼 수 있다.

문제 링크

boj/2096

소스코드

PS/2096 .java

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

public class Main {
    static int[][] d;
    static int[][] d2;
    static int[][] arr;

    static int solve(int i, int j) {
        if (d[i][j] != -1)
            return d[i][j];
        if (i == n - 1)
            return arr[i][j];
        d[i][j] = 0;
        if (j == 0)
            d[i][j] = arr[i][j] + Math.max(solve(i + 1, 0), solve(i + 1, 1));
        else if (j == 1)
            d[i][j] = arr[i][j] + Math.max(solve(i + 1, 0), Math.max(solve(i + 1, 1), solve(i + 1, 2)));
        else if (j == 2)
            d[i][j] = arr[i][j] + Math.max(solve(i + 1, 1), solve(i + 1, 2));
        return d[i][j];
    }

    static int solve2(int i, int j) {
        if (d2[i][j] != 987654321)
            return d2[i][j];
        if (i == n - 1)
            return arr[i][j];
        d2[i][j] = 0;
        if (j == 0)
            d2[i][j] = arr[i][j] + Math.min(solve2(i + 1, 0), solve2(i + 1, 1));
        else if (j == 1)
            d2[i][j] = arr[i][j] + Math.min(solve2(i + 1, 0), Math.min(solve2(i + 1, 1), solve2(i + 1, 2)));
        else if (j == 2)
            d2[i][j] = arr[i][j] + Math.min(solve2(i + 1, 1), solve2(i + 1, 2));
        return d2[i][j];
    }

    static int n;
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        n = Integer.parseInt(br.readLine());
        d = new int[n][3];
        d2 = new int[n][3];
        arr = new int[n][3];
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            arr[i][0] = Integer.parseInt(st.nextToken());
            arr[i][1] = Integer.parseInt(st.nextToken());
            arr[i][2] = Integer.parseInt(st.nextToken());
            Arrays.fill(d[i], -1);
            Arrays.fill(d2[i], 987654321);
        }
        int max = Math.max(Math.max(solve(0, 0), solve(0, 1)), solve(0, 2));
        int min = Math.min(Math.min(solve2(0, 0), solve2(0, 1)), solve2(0, 2));
        System.out.println(max + " " + min);


    }
}