#백준_2096 내려가기 - Java 자바

#유형 : 다이나믹 프로그래밍

#난이도 : 골드 4

# 다이나믹 프로그래밍의 전형적인 문제로, 현 위치에서 어디로 내려갈 수 있는가를 따지면 된다. 인덱스를 1,2,3 이라고 하였을 때

 

1) 인덱스 1에서는 아래층의 1,2 로 이동할 수 있다 => dp[i][1] = Math.max or min(dp[i-1][1], dp[i-1][2]) + arr[i][1])

2) 인덱스 2에서는 아래층의 1,2,3으로 이동할 수 있다 => dp[i][2] = Math.max or min(dp[i-1][1], dp[i-1][2], dp[i-1][3]) + arr[i][2])

3) 인덱스 3에서는 아래층의 2,3 으로 이동할 수 있다 => dp[i][3] = Math.max or min(dp[i-1][2], dp[i-1][3]) + arr[i][3])

 

이 점화식으로 알고리즘을 짜면 된다. 맨 처음에 생각없이 배열을 [N][N] 사이즈로 했다가 메모리초과가 계속 발생해서 왜 그런지 한참 수정했다.. 2) 를 굳이 줄이자면 min이던, max던 dp[i][1]에서 max 또는 min값을 미리 계산했기 때문에 Math.max or min(dp[i][1] - arr[i][1], dp[i-1][3]) + arr[i][2] 로 나타낼 수 있다.

 

 

package bj;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class p2096 {
    static int N;
    static int arr[][];
    static int max[][], min[][];
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        arr = new int[N+1][4];
        max = new int[N+1][4];
        min = new int[N+1][4];
        
        for(int i=1; i<=N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j=1; j<=3; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        
        for(int i=1; i<=N; i++) {
            max[i][1] += Math.max(max[i-1][1], max[i-1][2]) + arr[i][1];
            max[i][2] += Math.max(Math.max(max[i-1][1], max[i-1][2]), max[i-1][3]) + arr[i][2];
            max[i][3] += Math.max(max[i-1][2], max[i-1][3]) + arr[i][3];
            
            min[i][1] += Math.min(min[i-1][1], min[i-1][2]) + arr[i][1];
            min[i][2] += Math.min(Math.min(min[i-1][1], min[i-1][2]), min[i-1][3]) + arr[i][2];
            min[i][3] += Math.min(min[i-1][2], min[i-1][3]) + arr[i][3];
        }
        
        int maxValue = 0, minValue = Integer.MAX_VALUE;
        for(int i=1; i<=3; i++) {
            maxValue = Math.max(maxValue, max[N][i]);
            minValue = Math.min(minValue, min[N][i]);
        }
        
        System.out.println(maxValue+" " +minValue);
    }
}