[BOJ] 2096 - 내려가기

-개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다.

 

문제

www.acmicpc.net/problem/2096

2096번: 내려가기

난이도: 골드 4

사용언어: JAVA

 

풀이

이 문제는 [1149번 - RGB거리]와 굉장히 유사한 문제입니다. 기본적인 풀이는 아래의 RGB거리에 대한 풀이에서 확인하실 수 있습니다.

 

jooona.tistory.com/64

[BOJ] 1149 - RGB거리

RGB거리와 다른 점이라면, 바로 다음 레벨로 이동할 수 있는 칸의 위치와 최댓값과 최솟값을 모두 구해야 한다는 점뿐입니다. 최댓값과 최솟값을 모두 구하기 위해 두 개의 이차원 배열을 사용해 다이나믹 프로그래밍을 수행하였습니다.

 

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;
 
class Main {
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());
        int i, j;
        int [][]max = new int[N][3]; // 최댓값을 구하기 위한 dp 배열
        int [][]min = new int[N][3]; // 최솟값을 구하기 위한 dp 배열
        int []arr = new int[3]; // 매 줄 마다 입력 값을 저장하기 위한 배열
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(j=0;j<3;j++){
            max[0][j] = Integer.parseInt(st.nextToken()); // max 배열과 min 배열 모두 첫 줄은 입력 그대로 사용
            min[0][j] = max[0][j];
        }
        
        for(i=1;i<N;i++){
            st = new StringTokenizer(br.readLine());
            for(j=0;j<3;j++){
                arr[j] = Integer.parseInt(st.nextToken());
            }
            max[i][0] = Math.max(max[i-1][0],max[i-1][1]) + arr[0]; // 가장 왼쪽 칸에는 윗 행의 가장 왼쪽 칸과 가운데 칸에서만 값을 받아올 수 있음
            max[i][1] = Math.max(max[i-1][0],Math.max(max[i-1][1],max[i-1][2]))+ arr[1]; // 가운데 칸에는 윗 행의 모든 칸에서 값을 받아올 수 있음
            max[i][2] = Math.max(max[i-1][1],max[i-1][2])+ arr[2]; // 가장 오른쪽 칸에는 윗 행의 가장 오른쪽 칸과 가운데 칸에서만 값을 받아올 수 있음
            min[i][0] = Math.min(min[i-1][0],min[i-1][1])+ arr[0];
            min[i][1] = Math.min(min[i-1][0],Math.min(min[i-1][1],min[i-1][2]))+ arr[1];
            min[i][2] = Math.min(min[i-1][1],min[i-1][2])+ arr[2];
        }
 
        Arrays.sort(max[N-1]); // max 배열의 가장 아래 행 소팅
        Arrays.sort(min[N-1]); // min 배열의 가장 아래 행 소팅
        bw.write(String.valueOf(max[N-1][2])+ " "); // max 배열의 가장 아래 행에서 최댓값 출력
        bw.write(String.valueOf(min[N-1][0])+"\n"); // min 배열의 가장 아래 행에서 최솟값 출력
        bw.flush();
    }
}