[BOJ] 2096 - 내려가기 (Java)

• 다이나믹 프로그래밍
• 슬라이딩 윈도우

1. 문제

• 주어진 게임 보드에서 맨 위부터 맨 아래까지 이동하면서 각 칸의 숫자를 더해가며 최대값과 최소값을 찾는 문제
  

2. Idea

• DP를 사용하여 각 칸을 방문하면서 그 위치까지의 최대값과 최소값을 저장
• 현재 위치의 최대값 = 바로 이전 위치의 최대값과 현재 위치의 숫자를 더한 값 중 최대값
• 현재 위치의 최소 = 바로 이전 위치의 최소값과 현재 위치의 숫자를 더한 값 중 최소값

3. 풀이

3.1. 변수 선언 및 초기화

• n: 보드의 크기
• n행 3열의 2차원 배열(board) 생성
• 각 행은 게임 보드의 각 줄을 나타내고, 열은 각 줄에서의 숫자를 나타냄

Scanner sc = new Scanner(System.in);
        
int n = sc.nextInt();
int[][] board = new int[n + 1][3];
for(int i = 1; i <= n; i++) {
	for(int j = 0; j < 3; j++) {
		board[i][j] = sc.nextInt();
	}
}

3.2. 최소/최대값을 저장할 2차원 배열 생성

• maxDp: 최대값을 저장하는 2차원 배열
• minDp: 최소값을 저장하는 2차원 배열
• 배열들의 크기는 n+1 -> 인덱스 1부터 시작
• 각 배열의 행은 보드의 행을 나타내고, 열은 보드의 열을 나타냄

int[][] minDp = new int[n + 1][3];
int[][] maxDp = new int[n + 1][3];

3.3. 변수 선언 및 초기화

• 각 행의 각 열에 대해 최대값과 최소값을 계산
• 현재 위치의 최대값 = 이전 위치의 최대값과 현재 위치의 숫자를 더한 값 중에서 최대값
• 현재 위치의 최소값 = 이전 위치의 최소값과 현재 위치의 숫자를 더한 값 중에서 최소값

        for(int i = 1; i <= n; i++) {
            maxDp[i][0] += Math.max(maxDp[i - 1][0], maxDp[i - 1][1]) + board[i][0];
            maxDp[i][1] += Math.max(Math.max(maxDp[i - 1][0], maxDp[i - 1][1]), maxDp[i - 1][2]) + board[i][1];
            maxDp[i][2] += Math.max(maxDp[i - 1][1], maxDp[i - 1][2]) + board[i][2];
            
            minDp[i][0] += Math.min(minDp[i - 1][0], minDp[i - 1][1]) + board[i][0];
            minDp[i][1] += Math.min(Math.min(minDp[i - 1][0], minDp[i - 1][1]), minDp[i - 1][2]) + board[i][1];
            minDp[i][2] += Math.min(minDp[i - 1][1], minDp[i - 1][2]) + board[i][2];
        }
        
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        for(int i = 0; i < 3; i++) {
            min = Math.min(min, minDp[n][i]);
            max = Math.max(max, maxDp[n][i]);
        }

3.4. 변수 선언 및 초기화

• 마지막으로 계산된 최대값과 최소값을 찾는다.

int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
for(int i = 0; i < 3; i++) {
	min = Math.min(min, minDp[n][i]);
	max = Math.max(max, maxDp[n][i]);
}

3.4. 결과 출력

• 맨 아래 행에서의 최대값과 최소값을 출력

System.out.println(max + " " + min);

4. 전체코드

public class Main {
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        int[][] board = new int[n + 1][3];
        for(int i = 1; i <= n; i++) {
            for(int j = 0; j < 3; j++) {
                board[i][j] = sc.nextInt();
            }
        }
 
        int[][] minDp = new int[n + 1][3];
        int[][] maxDp = new int[n + 1][3];
        for(int i = 1; i <= n; i++) {
            maxDp[i][0] += Math.max(maxDp[i - 1][0], maxDp[i - 1][1]) + board[i][0];
            maxDp[i][1] += Math.max(Math.max(maxDp[i - 1][0], maxDp[i - 1][1]), maxDp[i - 1][2]) + board[i][1];
            maxDp[i][2] += Math.max(maxDp[i - 1][1], maxDp[i - 1][2]) + board[i][2];
            
            minDp[i][0] += Math.min(minDp[i - 1][0], minDp[i - 1][1]) + board[i][0];
            minDp[i][1] += Math.min(Math.min(minDp[i - 1][0], minDp[i - 1][1]), minDp[i - 1][2]) + board[i][1];
            minDp[i][2] += Math.min(minDp[i - 1][1], minDp[i - 1][2]) + board[i][2];
        }
        
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        for(int i = 0; i < 3; i++) {
            min = Math.min(min, minDp[n][i]);
            max = Math.max(max, maxDp[n][i]);
        }
        System.out.println(max + " " + min);
    }
}