[java] 프로그래머스 - 정수 삼각형

문제

프로그래머스-정수 삼각형
삼각형의 꼭대기에서 바닥까지 이어지는 경로 중 거쳐간 숫자의 합이 가장 큰 경우일 때 값을 찾는 문제

• 제한 사항
  삼각형의 높이는 1 이상 500이하이다
  삼각형을 이루고 있는 숫자는 0 이상 0,000 이하의 정수이다

• 예시
  
  최상단 꼭대기 값 (7)에서 (3)-(8)-(7)-(5) 순으로 내려오면 합이 30으로 최대이다

풀이

상단말고 최하단부터 시작해서 올라가는 방법으로 풀었다
최하단의 왼쪽에서 첫번째 5의 경우, 왼쪽 상단은 2, 오른쪽 상단은 7이다
이때 7을 더했을때의 합이 가장 크므로 메모배열에서 7이있는 자리에 5+7인 12를 넣어준다
5의 오른쪽에 있는 2에서 왼쪽 상단 7, 오른쪽 상단 4의 경우 왼쪽과 더했을때 합이 더 크다
이때 2+7=9이지만 메모배열의 7이있는 자리에 12가 이미 있다
12는 9보다 크므로 저장하지않는다
하단에서부터 한줄 위에까지 반복한 다음, 메모배열의 꼭대기 값을 출력한다

주의
입력받은 삼각형을 배열에 적용하면 왼쪽으로 치우쳐진, 📐이런 모양이 된다
인덱스를 적용할때 왼쪽상단은 idx-1, 오른쪽 상단은 idx가 된다

소스코드

class Solution {
  public int solution(int[][] triangle) {
		int[][] memo = new int[triangle.length][triangle.length]; // 메모배열은 ㅁ모양으로 만듦
		memo[memo.length - 1] = triangle[triangle.length - 1]; // 제일 하단 복사
		for (int i = triangle.length - 1; i > 0; i--) { // i-1을 할 것이므로 0포함 x
			for (int j = 0; j < triangle[i].length; j++) {
				if (j != 0 && memo[i][j] + triangle[i - 1][j - 1] > memo[i - 1][j - 1]) { // 제일 좌측은 j-1이 없으므로
					memo[i - 1][j - 1] = memo[i][j] + triangle[i - 1][j - 1];
				}
				if (j != triangle[i].length - 1 && memo[i][j] + triangle[i - 1][j] > memo[i - 1][j]) { // 현재줄의 윗줄은 j가 없으므로
					memo[i - 1][j] = memo[i][j] + triangle[i - 1][j];
				}
			}
		}
		return memo[0][0]; //꼭대기 리턴
	}
}