[백준] 1932 정수 삼각형

문제 출처: www.acmicpc.net/problem/1932

1932번: 정수 삼각형

: 정수 삼각형의 맨 위에서 아래로 내려오면수 선택된 수의 합을 최대로 만들어야 한다.

: 먼저 맨 위의 값을 미리 저장해놓고 아래에서 위를 바라보며 왼쪽과 오른쪽 중 큰 수를 더해주면 밑으로 내려가면된다.

: 그러면 마지막 줄에 최종 값들이 저장되고 그 중에서 가장 큰 값이 답이 된다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder sb = new StringBuilder();
	static StringTokenizer st; 
	public static void main(String[] args) throws NumberFormatException, IOException {
		int N = Integer.parseInt(br.readLine());
		int[][] map = new int[N][N];
		for(int i = 0; i < N; i++)
			Arrays.fill(map[i], -1);
		for(int i = 0; i < N; i++) {
			String[] tmp = br.readLine().split(" ");
			for(int j = 0, size = tmp.length; j < size; j++) {
				map[i][j] = Integer.parseInt(tmp[j]);
			}
		}
		
//		for(int[] sub : map){
//			System.out.println(Arrays.toString(sub));
//		}
		
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < N; j++) {
				if(i == 0 && j == 0 ) continue;
				int max = Integer.MIN_VALUE;
				if(map[i][j] != -1) {
					if(i-1 >= 0 && j-1 >= 0 && map[i-1][j-1] > max) max = map[i-1][j-1];
					if(i-1 >= 0 && map[i-1][j] > max) max = map[i-1][j];
					map[i][j] += max;
				}
			}
		}
//		for(int[] sub : map){
//			System.out.println(Arrays.toString(sub));
//		}
		int res = Integer.MIN_VALUE;
		for(int i = 0; i < N; i++)
			res = Math.max(res, map[N-1][i]);
		System.out.println(res);
		
	}
}