[프로그래머스 / Level3] 정수 삼각형 (Java)

문제 보기

사용한 것

• 큰 문제를 작은 문제로부터 해결해나가기 위한 DP 사용.

풀이 방법

• 삼각형의 가장 윗 부분부터 점차적으로 문제를 해결할 것이다.
• i = 0 부터 for문을 돌리면서 sum()을 호출한다.
  • sum()은 i 번째 줄과 i + 1 번째 줄을 더하여 나온 배열을 반환한다.
  • 처음에는 왼쪽 아래 대각선으로 두 배열을 더해나간다.
  • 두 번째에는 오른쪽 아래 대각선으로 두 배열을 더해 나가면서 처음 더한 결과 값과 비교하여 크면 넣어준다.
• 이 과정을 triangle.length - 2까지 반복하면 row에 더하면서 내려온 최대 값들이 저장된다.
• 마지막으로 다시 row를 돌면서 가장 큰 값을 max에 저장하여 반환한다.

코드

class Solution {

    public int solution(int[][] triangle) {
        int[] row = triangle[0];
        for (int i = 0; i < triangle.length - 1; i++) {
            triangle[i] = row;
            row = sum(triangle, i);
        }

        int max = row[0];
        for (int i = 1; i < row.length; i++) {
            if (row[i] > max) {
                max = row[i];
            }
        }

        return max;
    }

    int[] sum(int[][] triangle, int index) {
        int[] nextRow = new int[index + 2];
        for (int i = 0; i <= index; i++) {
            nextRow[i] = triangle[index][i] + triangle[index + 1][i];
        }

        for (int i = 0; i <= index; i++) {
            nextRow[i + 1] = Math.max(
                triangle[index][i] + triangle[index + 1][i + 1],
                nextRow[i + 1]
            );
        }

        return nextRow;
    }
}