[백준] 내려가기

참고 : www.acmicpc.net/problem/2096

2096번: 내려가기

 

- dp 문제

- dp[i][0] : dp[i-1][0] + dp[i-1][1] ( = i-1번째의 최소값, 최대값 (0번, 1번이 해당 i번째로 이동가능)) + s[i][0] 

- dp[i][1] : dp[i-1][0] + dp[i-1][1] + dp[i-1][2] ( = i-1번째의 최소값, 최대값 (0번, 1번, 2번이 해당 i번째로 이동가능)) + s[i][1] 

- dp[i][2] : dp[i-1][1] + dp[i-1][2] ( = i-1번째의 최소값, 최대값 (1번, 2번이 해당 i번째로 이동가능)) + s[i][2] 

 

import java.util.*;

public class Solution {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[][] s = new int[N+1][3];
        int[][] dpMin = new int[N+1][3];
        int[][] dpMax = new int[N+1][3];
        for (int i = 1; i <= N; i++) {
            s[i][0] = sc.nextInt();
            s[i][1] = sc.nextInt();
            s[i][2] = sc.nextInt();
        }

        for (int i = 1; i <= N; i++) {
            // 최소 dp
            dpMin[i][0] = Math.min(dpMin[i-1][0], dpMin[i-1][1]) + s[i][0];
            dpMin[i][1] = Math.min(dpMin[i-1][0], Math.min(dpMin[i-1][1], dpMin[i-1][2])) + s[i][1];
            dpMin[i][2] = Math.min(dpMin[i-1][1], dpMin[i-1][2]) + s[i][2];
            // 최대 dp
            dpMax[i][0] = Math.max(dpMax[i-1][0], dpMax[i-1][1]) + s[i][0];
            dpMax[i][1] = Math.max(dpMax[i-1][0], Math.max(dpMax[i-1][1], dpMax[i-1][2])) + s[i][1];
            dpMax[i][2] = Math.max(dpMax[i-1][1], dpMax[i-1][2]) + s[i][2];
        }
        System.out.print(Math.max(dpMax[N][0], Math.max(dpMax[N][1], dpMax[N][2])));
        System.out.print(" ");
        System.out.print(Math.min(dpMin[N][0], Math.min(dpMin[N][1], dpMin[N][2])));
    }
}