[프로그래머스][JAVA][Lv. 3] 정수 삼각형

문제 설명

https://school.programmers.co.kr/learn/courses/30/lessons/43105

---

제한 사항

---

입출력 예

---

풀이

class Solution {
    public int solution(int[][] triangle) {
        int answer = 0;
        int[] result = new int[] { triangle[0][0] };
        
        for (int i = 0; i < triangle.length - 1; i++) {
            int[] tempResult = new int[i + 2];
            
            for (int j = 0; j < triangle[i].length; j++) {
                int pre = result[j] + triangle[i + 1][j];
                int post = result[j] + triangle[i + 1][j + 1];
                
                tempResult[j] = Math.max(tempResult[j], pre);
                tempResult[j + 1] = Math.max(tempResult[j + 1], post);
                answer = Math.max(Math.max(pre, post), answer);
            }
            result = tempResult;
        }
        
        return answer;
    }
}

---

후기

다이나믹 프로그래밍의 정석같은 문제이다. 평소에 DP 공부를 안 했었기 때문에 많이 헤맸는데 이번에 이 문제를 풀면서 조금 감을 잡았다. 처음에는 완전 탐색으로 풀었는데 메모리 초과나 시간 초과가 되어 DP를 사용하게 되었고 ArrayList를 사용하면서 또 시간 초과가 나서 배열로 바꾸니 통과됐다.