[BOJ 1932번] 정수 삼각형(JAVA)

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

1932번: 정수 삼각형

import java.util.*;
import java.io.*;

public class Main {
	static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
	static StringBuilder sb=new StringBuilder();
	static int[][] triangle;
	
	public static void main(String args[]) throws Exception {
		int n=Integer.parseInt(br.readLine());
		triangle=new int[n][n];
		int result=0;
		for(int i=0;i<n;i++) {
			String str[]=br.readLine().split(" ");
			for(int j=0;j<=i;j++) {
				triangle[i][j]=Integer.parseInt(str[j]);
				if(i!=0) {
					if(j==0) triangle[i][j]+=triangle[i-1][j]; // 정수 삼각형의 왼쪽 테두리 부분
					else if(j==i) triangle[i][j]+=triangle[i-1][j-1]; //정수 삼각형의 오른쪽 테두리 부분
					else triangle[i][j]+=Math.max(triangle[i-1][j], triangle[i-1][j-1]);
					if(result<triangle[i][j]) result=triangle[i][j];
				}
			}
		}
		System.out.println(result);
	}
}

 삼각형의 맨 위층부터 한 층씩 내려가면서 접근을 해보았습니다.

삼각형에서 가장 맨 아래 층 가장 왼쪽과 가장 오른쪽 데이터에 접근하기 위해서는 왼쪽 사이드의 요소들끼리만 더하거나, 오른쪽 사이드의 요소들만 더하면서 내려가야 합니다.

그렇기 때문에 왼쪽 사이드와 오른쪽 사이드의 요소들만 더했을 때 상황은 if 문을 통해서 따로 값을 계산해주었습니다.

그리고 그 이외의 상황에서는 현재 층과 현재 층 1층 위의 왼쪽 오른쪽 요소 중 최댓값과 더하고 그 값을 현재 층의 triangle[i][j]에 저장을 해주었습니다.

이런식으로 데이터들의 합을 triangle 배열에 저장하면서 내려오는 방식으로 데이터를 계산했습니다.

그리고 그 중 최댓값을 result 변수에 저장해서 최댓값을 저장했습니다.