[백준]2096: 내려가기 - JAVA

[백준]2096: 내려가기

www.acmicpc.net/problem/2096

2096번: 내려가기

풀이

DP문제로 프로그래머스의 '정수 삼각형'문제와 매우 유사하다.

정수 삼각형은 최대값만 찾았다면 이번 문제는 최대, 최소값을 모두 찾는 문제이다.

 

합을 누적시킬때 최대값을 누적시키는 maxDp, 최솟값을 누적시키는 minDp배열을 만들어 주었다. 이때 한 줄당 총 3개의 숫자가 올 수 있으므로 3개의 경우로 나누어서 누적시켜주었다.

 

각각의 위치에서 누적시킬 인덱스는 다음과 같다.

 

현재 인덱스가 [n][0]일때 -> [n - 1][0]과 [n - 1][1]중의 최대/최소값 + [n][0]

[n - 1][0]	[n - 1][1]
[n][0]

 

현재 인덱스가 [n][1]일때 -> [n - 1][0]과 [n - 1][1]과 [n - 1][2]중의 최대/최소값 + [n][0]

[n - 1][0]	[n - 1][1]	[n - 1][2]
	[n][1]

 

 

현재 인덱스가 [n][2]일때 -> [n - 1][1]과 [n - 1][2]중의 최대/최소값 + [n][0]

	[n - 1][1]	[n - 1][2]
		[n][2]

 

위 세가지 경우밖에 없다. 그러므로 세가지 경우만 따지면서 코드를 작성해 주었다. 이때 누적 합을 계산해 주기 위해서 배열의 크기를 [n + 1][3]으로 잡아주었다. 첫 번째 열에서도 최대/최소값을 계산해 줄 수 있도록 하였다. 

 

위의 방법으로 누적 합을 구한 다음 마지막 열에서의 최대, 최소값을 찾아 그 값을 정답으로 출력해 주었다.

 

DP문제 중에서 그나마 쉬운 난이도라고 생각되는 문제였다!

 

코드

import java.util.*;
 
public class Main {
 
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        
        int n = scan.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] = scan.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);
    }
}