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

• 정수 삼각형

풀이과정

1. 삼각형의 가장 아래쪽에서부터 두 줄을 선택한다. 아랫줄을 currentLine, 그 윗 줄을 nextLine으로 설정.
2. currentLine[i] 또는 currentLine[i + 1] 중에서 큰 값을 선택하여 nextLine[i] 에 더한다.
3. nextLine 이 삼각형의 꼭대기를 가리킬 때 까지 currentLine, nextLine을 삼각형의 위로 올려가며 2번 과정을 반복한다.
4. 삼각형의 꼭대기에 최댓값이 저장되므로 이를 반환한다.

• 위 과정과는 반대로 위에서부터 아래쪽으로 내려가면서 계산할 수도 있지만, 이렇게 풀이를 진행 할 경우 삼각형의 가장 아랫줄을 순회하면서 최댓값을 찾는 과정이 추가되므로 비효율적이다.

Code

class Solution {
    public int solution(int[][] triangle) {
        for (int i = triangle.length - 1; i > 0; i--) {
            int[] currentLine = triangle[i];
            int[] nextLine = triangle[i - 1];

            for (int j = 0; j < nextLine.length; j++) {
                int left = currentLine[j];
                int right = currentLine[j + 1];
                  nextLine[j] += Math.max(left, right);
            }
        }

        return triangle[0][0];
    }
}

결과