[백준] BOJ 2096 내려가기 (골드 5)

문제

---

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

2096번: 내려가기

---

해설

---

---

1. 현재 row에 올 수 있는 row - 1값 중 큰 값 + 현재 값을 dp를 통해 업데이트
2. 현재 왼쪽 : max(dpMax[row - 1][0], dpMax[row - 1][1]) + arr[row][0]
3. 현재 가운데 : max(dpMax[row - 1][0], dpMax[row - 1][1], dpMax[row - 1][2]) + arr[row][1]
4. 현재 오른쪽 : max(dpMax[row - 1][1], ddpMax[row - 1][2]) + arr[row][2]
5. 마지막에 max(dpMax[N][0], dpMax[N][1], dpMax[N][2]) 출력
6. 최소는 max -> min으로 변경하고, dpMax dpMin배열을 사용

---

코드 (DP)

---

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    static StringBuilder sb = new StringBuilder();
    static int[][] dpMax;
    static int[][] dpMin;
    static int[][] arr;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        int max = 0;
        int min = Integer.MAX_VALUE;

        dpMax = new int[N + 1][3];
        dpMin = new int[N + 1][3];
        arr = new int[N + 1][3];
        for (int i = 1; i <= N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < 3; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
            dpMax[i][0] = Math.max(dpMax[i - 1][0], dpMax[i - 1][1]) + arr[i][0];
            dpMax[i][1] = Math.max(dpMax[i][0] - arr[i][0], dpMax[i - 1][2]) + arr[i][1];
            dpMax[i][2] = Math.max(dpMax[i - 1][1], dpMax[i - 1][2]) + arr[i][2];;

            dpMin[i][0] = Math.min(dpMin[i - 1][0], dpMin[i - 1][1]) + arr[i][0];
            dpMin[i][1] = Math.min(dpMin[i][0] - arr[i][0], dpMin[i - 1][2]) + arr[i][1];;
            dpMin[i][2] = Math.min(dpMin[i - 1][1], dpMin[i - 1][2]) + arr[i][2];;
        }

        for (int i = 0; i < 3; i++) {
            max = Math.max(max, dpMax[N][i]);
            min = Math.min(min, dpMin[N][i]);
        }
        sb.append(max).append(" ").append(min);
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }
}

---

결론

---

문제 자체가 직관적이라 바로 해결할 수 있었던 문제!

---