백준 2096번 내려가기 JAVA

링크텍스트

설명

주어진 비용 배열에서 최소 및 최대 비용을 구하는 동적 계획법(DP) 문제를 해결했다.
maxdp[i][0] = Math.max(maxdp[i - 1][0], maxdp[i - 1][1]) + arr[i][0];
maxdp[i][1] = Math.max(Math.max(maxdp[i - 1][0], maxdp[i - 1][1]), maxdp[i - 1][2]) + arr[i][1];
maxdp[i][2] = Math.max(maxdp[i - 1][1], maxdp[i - 1][2]) + arr[i][2]; 를 이용해 각 dp의 값을 구한다.
슬라이딩 윈도우 알고리즘을 사용해서 답을 풀 수도 있다.

코드

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

public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int n = Integer.parseInt(br.readLine());

        int[][] arr = new int[n][3];
        int[][] maxdp = new int[n][3];
        int[][] mindp = new int[n][3];

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < 3; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        maxdp[0] = arr[0].clone();
        mindp[0] = arr[0].clone();

        for (int i = 1; i < n; i++) {
            maxdp[i][0] = Math.max(maxdp[i - 1][0], maxdp[i - 1][1]) + arr[i][0];
            maxdp[i][1] = Math.max(Math.max(maxdp[i - 1][0], maxdp[i - 1][1]), maxdp[i - 1][2]) + arr[i][1];
            maxdp[i][2] = Math.max(maxdp[i - 1][1], maxdp[i - 1][2]) + arr[i][2];

            mindp[i][0] = Math.min(mindp[i - 1][0], mindp[i - 1][1]) + arr[i][0];
            mindp[i][1] = Math.min(Math.min(mindp[i - 1][0], mindp[i - 1][1]), mindp[i - 1][2]) + arr[i][1];
            mindp[i][2] = Math.min(mindp[i - 1][1], mindp[i - 1][2]) + arr[i][2];
        }
        
        System.out.println(Math.max(Math.max(maxdp[n - 1][0], maxdp[n - 1][1]), maxdp[n - 1][2])+" "+Math.min(Math.min(mindp[n - 1][0], mindp[n - 1][1]), mindp[n - 1][2]));
    }
}

슬라이딩 윈도우 코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int n = Integer.parseInt(br.readLine());

        int[] arr = new int[3];  // 현재 행의 값
        int[] maxdp = new int[3];  // 최대값
        int[] mindp = new int[3];  // 최소값
        int[] prevMax = new int[3];  // 이전 행의 최대값
        int[] prevMin = new int[3];  // 이전 행의 최소값

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            // 새로운 행의 값을 읽어옴
            arr[0] = Integer.parseInt(st.nextToken());
            arr[1] = Integer.parseInt(st.nextToken());
            arr[2] = Integer.parseInt(st.nextToken());

            if (i == 0) {
                // 첫 번째 행은 초기값 설정
                prevMax[0] = arr[0];
                prevMax[1] = arr[1];
                prevMax[2] = arr[2];
                prevMin[0] = arr[0];
                prevMin[1] = arr[1];
                prevMin[2] = arr[2];
            } else {
                // 최대값 업데이트
                maxdp[0] = Math.max(prevMax[0], prevMax[1]) + arr[0];
                maxdp[1] = Math.max(Math.max(prevMax[0], prevMax[1]), prevMax[2]) + arr[1];
                maxdp[2] = Math.max(prevMax[1], prevMax[2]) + arr[2];

                // 최소값 업데이트
                mindp[0] = Math.min(prevMin[0], prevMin[1]) + arr[0];
                mindp[1] = Math.min(Math.min(prevMin[0], prevMin[1]), prevMin[2]) + arr[1];
                mindp[2] = Math.min(prevMin[1], prevMin[2]) + arr[2];

                // 이전 행 값을 갱신
                prevMax[0] = maxdp[0];
                prevMax[1] = maxdp[1];
                prevMax[2] = maxdp[2];

                prevMin[0] = mindp[0];
                prevMin[1] = mindp[1];
                prevMin[2] = mindp[2];
            }
        }

        // 결과 출력
        System.out.println(Math.max(Math.max(prevMax[0], prevMax[1]), prevMax[2]) + " " +
                           Math.min(Math.min(prevMin[0], prevMin[1]), prevMin[2]));
    }
}

참고 글
https://velog.io/@mendel/%EB%B0%B1%EC%A4%80-2096-%EB%82%B4%EB%A0%A4%EA%B0%80%EA%B8%B0-java