[백준 알고리즘] 2096번: 내려가기 (Java / 자바)

1차원 dp로 해결할 수 있는 문제이다.

요즘 이런 유형이 많이 나오는 거 같다. 얼마 전 본 코테에서도 비슷한 문제가 나왔는데..
대충 아래 -> 위 or 위 -> 아래 로만 가면서 인접한 칸과 대각에 위치한 칸 중에 최선의 값으로 가는
그런 유형이라고 보면되겠다

for문을 한번만 돌면서 max, min을 한 사이클에 처리하도록 짰다.

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

public class boj_2096 {
    static int N;
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int[][] board;
    static int[][] dpMax, dpMin;
    /*
    왼쪽에 있을 때: 아래, 중간
    중간일때: 모두
    우측에 있을 때: 아래, 중간

    한줄에서 한번에 처리해야함
    가장 좌측에 올 수 있는 값의 최선
    중앙에 올 수 있는 값의 최선
    우측에 올수 있는 값의 최선
    이렇게 한 칸씩 업데이트(위 칸 기반)
     */
    public static void main(String[] args) throws IOException {
        N = Integer.parseInt(br.readLine());
        board = new int[N][3];
        for (int i=0; i<N; i++) {
            st = new StringTokenizer(br.readLine());
            board[i][0] = Integer.parseInt(st.nextToken());
            board[i][1] = Integer.parseInt(st.nextToken());
            board[i][2] = Integer.parseInt(st.nextToken());
        }

        dpMax = new int[N][3];
        dpMin = new int[N][3];  // dp 테이블 초기화
        dpMax[0] = board[0]; // 첫줄은 그대로
        dpMin[0] = board[0];

        for (int i=1; i<N; i++) {
            /* 최대 값 계산 */
            // 1. 왼쪽 값 최선 (바로 내려오기, 중간에서 오기)
            dpMax[i][0] = Math.max(dpMax[i-1][0] + board[i][0], dpMax[i-1][1] + board[i][0]);

            // 2. 중간 값 최선 (왼쪽에서 오기, 바로 내려오기, 오른쪽에서 오기)
            dpMax[i][1] = Math.max(dpMax[i-1][0] + board[i][1], Math.max(dpMax[i-1][1] + board[i][1], dpMax[i-1][2] + board[i][1]));

            // 3. 오른쪽 값 최선 (중간에서 오기, 바로 내려오기)
            dpMax[i][2] = Math.max(dpMax[i-1][1] + board[i][2], dpMax[i-1][2] + board[i][2]);

            /* 최소 값 계산 */
            // 1. 왼쪽 값 최선 (바로 내려오기, 중간에서 오기)
            dpMin[i][0] = Math.min(dpMin[i-1][0] + board[i][0], dpMin[i-1][1] + board[i][0]);

            // 2. 중간 값 최선 (왼쪽에서 오기, 바로 내려오기, 오른쪽에서 오기)
            dpMin[i][1] = Math.min(dpMin[i-1][0] + board[i][1], Math.min(dpMin[i-1][1] + board[i][1], dpMin[i-1][2] + board[i][1]));

            // 3. 오른쪽 값 최선 (중간에서 오기, 바로 내려오기)
            dpMin[i][2] = Math.min(dpMin[i-1][1] + board[i][2], dpMin[i-1][2] + board[i][2]);
        }
        System.out.println(Math.max(dpMax[N-1][0], Math.max(dpMax[N-1][1], dpMax[N-1][2])) + " " + Math.min(dpMin[N-1][0], Math.min(dpMin[N-1][1], dpMin[N-1][2])));
    }
}

 

Java로 넘어온지 2개월차 .. 이제 다 익숙해졌는데 배열에서 max 안되는거 아쉽긴하다

dp 문제 많이 싫어했는데 계속 풀다보니 아는 유형이기만 하면, 구현하기가 편하고 시간도 얼마 안걸리는거 같다
이제 2차원 dp를 좀더 연습해야겟다