[BaekJoon] 백준 1932. 정수 삼각형- Java

 

각층을 1차원 배열로 지정하고 전체 삼각형을 2차원 배열로 바라본다 할때

 

n층의 i번째 배열은 d[n-1][i-1], d[n-1][i] 중 최대값과 합한 값이다. 

 

단 첫번째 요소와 마지막 요소는 경로가 1가지 뿐이다. 

 

import java.util.Scanner;

public class Main {
	public static void main(String args[]) {
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		int max = 0;
		int[][] array = new int[n][n];
		int[][] d = new int[n][n];
		
		
		array[0][0] = scan.nextInt();
		d[0][0] = array[0][0];
		max = d[0][0];
		
		for(int i = 1; i<n; i++) {			
			for(int j = 0; j<=i; j++) {
				array[i][j] = scan.nextInt();
				if(j == 0) d[i][j] = d[i-1][j];
				else if(j == i) d[i][j] = d[i-1][j-1];
				else d[i][j] = Math.max(d[i-1][j-1], d[i-1][j]);
				
				d[i][j] += array[i][j];
				
				if(d[i][j] > max)
					max = d[i][j];
			}
		}
	
		System.out.println(max);
	}
	


}