[백준] 2096 내려가기

문제보기

직전에 풀었던 종만북의 Triangle Path문제랑 같은 원리로 풀어주면 된다.

하단부터 스멀스멀 올라오면서 최적해를 가져가면 된다

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));
    int n = Integer.parseInt(br.readLine());
    int[][] map = new int[n][3];
    for(int i = 0 ; i < n ;i++){
      StringTokenizer st = new StringTokenizer(br.readLine());
      for(int j = 0 ; j < 3 ; j++){
        map[i][j] = Integer.parseInt(st.nextToken());
      }
    } 
		
    // 최대값을 담을 변수
    int[][] max = new int[n][3];
    // 최솟값을 담을 변수
    int[][] min = new int[n][3];
		
   	// 일단 최 하단 애들은 값 자체가 최대,최소값임
    for(int i = 0 ; i < 3 ; i++){
      max[n-1][i] = min[n-1][i] = map[n-1][i];
    }
		
    // 열 갯수가 3개로 고정이므로 머리쓰지 말고 그냥 쓰자 ^^
    for(int i = n-2 ; i >= 0 ; i-- ){
      // 아래 코드는 문제에 나오는 그림을 보면 이해할 수 있을것이다
      max[i][0] = map[i][0] + Math.max(max[i+1][0], max[i+1][1]);
      max[i][1] = map[i][1] + Math.max(max[i+1][0], Math.max(max[i+1][1], max[i+1][2]));
      max[i][2] = map[i][2] + Math.max(max[i+1][1], max[i+1][2]);

      min[i][0] = map[i][0] + Math.min(min[i+1][0], min[i+1][1]);
      min[i][1] = map[i][1] + Math.min(min[i+1][0], Math.min(min[i+1][1], min[i+1][2]));
      min[i][2] = map[i][2] + Math.min(min[i+1][1], min[i+1][2]);
    }

    int amax = 0;
    int amin = 900001; // n 최대가 10만이고, 각 칸은 9가 최대이므로 900000이 최악임

    for(int i = 0 ; i < 3 ; i++ ){
      if(max[0][i] > amax) amax = max[0][i];
      if(min[0][i] < amin) amin = min[0][i];
    }

    System.out.println(amax + " " + amin);
  }
}