정수삼각형 (Level 3)

이번문제는 기본적인 흐름대로 구현하여도 무난하게 풀 수 있는문제이다.

 

다만, 2차원 배열의 내부가 길이가 다 다르다는 점만 주의하면된다.

 

import java.util.*;

class Solution {
	public int solution(int[][] triangle) {
		int answer = 0;

		int n = triangle.length;
		List<int[]> arr = new ArrayList<int[]>(); // 루트노드부터 계산한 합만 들어가 리스트
		
		for(int i=0; i < n; i++) { // 초기화
			arr.add(new int[i+1]);
		}

		int[]a = arr.get(0); // 최초갑 세팅
		a[0] = triangle[0][0];

		for (int i = 1; i < triangle.length; i++) {
			for (int j = 0; j <= i; j++) { // i==j가 마지막인것 주의

				int leftX = i - 1; // 왼쪽 위 노드
				int leftY = j - 1; 

				int rightX = i - 1; // 오른쪽 위 노드
				int rightY = j;

				int max = -1;
				if (leftX >= 0 && leftY >= 0 && leftY <= leftX) { //범위
					int value = triangle[i][j] + arr.get(leftX)[leftY]; // 새로운값 + 위까지 더한값
					max = max > value ? max : value;
				}

				if (rightX >= 0 && rightY >= 0 && rightY <= rightX) {
					int value = triangle[i][j] + arr.get(rightX)[rightY]; // 새로운값 + 위까지 더한값
					max = max > value ? max : value; // 더 큰값으로 더해줘야함
				}

				arr.get(i)[j] = max; //큰값으로 적용
			}
		}
		
		for(int i=0; i < n; i++) { // 마지막 노드들 중에서 가장 큰값 반환
			answer = answer < arr.get(n-1)[i] ? arr.get(n-1)[i]: answer; 
		}

		return answer;
	}