[Java] 백준 1932 : 정수 삼각형

https://www.acmicpc.net/problem/1932

1932번: 정수 삼각형

---

 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택해서 더해가야 한다.

배열에는 아래처럼 저장되어 있다. 

7	0	0	0	0
3	8	0	0	0
8	1	0	0	0
2	7	4	4	0
4	5	2	6	5

여기서 그래프의 대각선 왼쪽 또는 대각선 오른쪽은 배열에서 자신의 바로 위에 있는 수 혹은 자신의 왼쪽위에 있는 수 이다. 

그래서 가장 왼쪽에 있는 수 즉, i=0인 경우 왼쪽 위는 존재 하지 않으므로 

		if(j==0) {
			arr[i][j]=arr[i-1][j]+arr[i][j];	
				}

바로 위의 수만 현재의 수와 더해서 대입한다. 

i!=0인 경우에는 겹치는 부분이 발생하므로 else문에 넣어 아래처럼 작성한다. 

rr[i][j]=Math.max(arr[i-1][j], arr[i-1][j-1])+arr[i][j];

 

<결론>

import java.util.*;

public class Main {
	
	static int N;
	static int[][] arr;
	
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		N=sc.nextInt();
		arr=new int[N][N];
		
		for(int i=0;i<N;i++) {
			for(int j=0;j<=i;j++) {
				arr[i][j]=sc.nextInt();
			}
		}
		for(int i=1;i<N;i++) {
			for(int j=0;j<=i;j++) {
				if(j==0) {
					arr[i][j]=arr[i-1][j]+arr[i][j];	
				}
				else {
					arr[i][j]=Math.max(arr[i-1][j], arr[i-1][j-1])+arr[i][j];
				}
			}
		}
		
		int max = Arrays.stream(arr[N-1]).max().getAsInt();
		System.out.println(max);				
		
	}// main()
	
}// class Main