[JAVA] 동적프로그래밍(DP) "정수 삼각형"

동적프로그래밍(Dynamic Programming)의 기본형이 되는 문제이다.

 

Math.max값을 이용하여 이전 인덱스의 값과 비교하여 주어진 배열에 직접 업데이트 하는 방식이다.

 

import java.util.Arrays;

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

        for (int height = 1; height < triangle.length; height++) {

            for (int i = 0; i < triangle[height].length; i++) {

                if (i == 0) {//맨왼쪽
                    triangle[height][0] += triangle[height - 1][0];
                } else if (i == triangle[height].length - 1) {//맨오른쪽
                    triangle[height][i] += triangle[height - 1][i - 1];//
                } else {
                        triangle[height][i] +=
                                Math.max(triangle[height - 1][i - 1], triangle[height - 1][i]);
                }
            }

        }

        int[] max_sum = triangle[triangle.length - 1];
        Arrays.sort(max_sum);
        answer = max_sum[max_sum.length - 1];

        return answer;
    }
}

1) 양쪽 끝의 인덱스에서는 그대로 값을 더해주고,

 

2) 나머지 사이에 있는 값들은 이전 높이(height-1)에서 i항과 i-1항의 값을 비교하여 큰 값을 더해준다.

 

그리고 가장 마지막 줄에 있는 triangle의 밑변 값들을 가져와서 오름차순으로 정렬.

 

이후 마지막 항에 있는 값이 최대값이므로 return해준다.

 

 

아래는 간결하게 만든 코드이다.

import java.util.*;
class Solution {
    public int solution(int[][] triangle) {
        for (int i = 1; i < triangle.length; i++) {
            triangle[i][0] += triangle[i-1][0];
            triangle[i][i] += triangle[i-1][i-1];
            for (int j = 1; j < i; j++) 
                triangle[i][j] += Math.max(triangle[i-1][j-1], triangle[i-1][j]);
        }

        return Arrays.stream(triangle[triangle.length-1]).max().getAsInt();
    }
}

이처럼 for문에서 if문을 사용하지않고 미리 양쪽 끝값을 사전에 처리하여 if문을 안쓰는 방식이 있다.

코드 상 보기에는 간결하나, 실제 실행속도에는 별 차이가 없다.

 

그리고, stream을 이용한 배열의 최댓값을 구하는 방식을 참고하면 좋겠다.(물론 스트림은 비추다.)

 

Arrays.stream(triangle[triangle.length-1]).max().getAsInt();