[Algorithm] 백준 DP 문제 - 내려가기(2096) 자바 풀이

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

이번 포스팅은 백준 DP 문제 내려가기 자바 풀이를 진행하도록 하겠습니다.

문제 출처: https://www.acmicpc.net/problem/2096

2096번: 내려가기

 

1. 풀이 소스

 

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

import static java.lang.Integer.parseInt;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int n = parseInt(br.readLine());
        int[][] map = new int[n][3];
        
        int[][][] dp = new int[n][3][2]; // 최대, 최소 저장 
        
        for (int row = 0; row < n; row++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int col = 0; col < 3; col++) {
                map[row][col] = parseInt(st.nextToken());        
            }
        }
        
        dp[0][0][0] = dp[0][0][1] = map[0][0]; // 초기화는 map에 있는 값으로 설정 
        dp[0][1][0] = dp[0][1][1] = map[0][1];
        dp[0][2][0] = dp[0][2][1] = map[0][2];
        
        for (int row = 1; row < n; row++) { // 왼쪽은 왼, 중앙 / 중앙은 왼, 중, 오 / 오른쪽은 중, 오 순서로 dp 진행 
            // 최대 
            dp[row][0][0] = Math.max(dp[row - 1][0][0], dp[row - 1][1][0]) + map[row][0];
            dp[row][1][0] = Math.max(Math.max(dp[row - 1][0][0], dp[row - 1][1][0]), dp[row - 1][2][0]) + map[row][1];
            dp[row][2][0] = Math.max(dp[row - 1][1][0], dp[row - 1][2][0]) + map[row][2];
        
            // 최소 
            dp[row][0][1] = Math.min(dp[row - 1][0][1], dp[row - 1][1][1]) + map[row][0];
            dp[row][1][1] = Math.min(Math.min(dp[row - 1][0][1], dp[row - 1][1][1]), dp[row - 1][2][1]) + map[row][1];
            dp[row][2][1] = Math.min(dp[row - 1][1][1], dp[row - 1][2][1]) + map[row][2];    
        }
        
        int max = Math.max(Math.max(dp[n - 1][0][0], dp[n - 1][1][0]), dp[n - 1][2][0]);
        int min = Math.min(Math.min(dp[n - 1][0][1], dp[n - 1][1][1]), dp[n - 1][2][1]);
    
        System.out.println(max + " " + min);
    }
}

 

2. 풀이 중점 사항

 

문제에서 요구하는 것은 최대, 최소를 출력하여야 하므로 dp를 3차원 배열로 선언하여 각각 최대, 최소를 매 상황에 맞게 구하는 것이 중요한 포인트였습니다.!

N이 최대 10만이고, 최대 숫자는 9 이므로 max의 범위는 90만이므로 int 3차원 배열로 설정하였습니다.

 

이상으로 백준 DP 문제 내려가기 풀이를 마치도록 하겠습니다. 감사합니다.!