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

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

프로그래머스

1. 코드

class Solution {
    static int[][] arr;
    public static int solution(int[][] triangle) {
        arr = new int[triangle.length][triangle[triangle.length - 1].length];
        return DP(triangle, 0, 0);
    }
    public static int DP(int[][] triangle, int row, int col) {
        if(row == triangle.length - 1) return triangle[row][col];
        else if(arr[row][col] > 0) return arr[row][col];
        else return arr[row][col] = triangle[row][col] + Math.max(DP(triangle, row + 1, col), DP(triangle, row + 1, col + 1));
    }
}

2. 설명

동적 계획법을 재귀로 구현하게되면 상당히 간단하게 해결되었습니다. row가 triangle의 최대 값이라면 해당 triangle을 반환하며 arr[row][col]이 존재하면 arr[row][col]을 반환합니다. arr[row][col]이 존재하지 않으면 triangle[row][col] + 자식 노드 2개중 가장 큰 값을 가진 값으로 저장합니다.
따라서 부모 노드의 값을 자식 노드에서 2개를 비교 후 저장하여 부모 노드의 값을 이미 저장했다면 빠르게 비교 후 저장이 가능합니다.

그림 1

그림 2

코드의 동작 방식을 위 그림들을 통해서 표현했는데 그림 1을 살펴보면 중간에 위치한 부모 노드 중 이미 계산이 완료된 부모 노드는 1번만 계산된 이후 바로 계산된 값을 가져오기에 시간 복잡도가 매우 크게 감소하게 됩니다.

3. 정리

1. 시간초과가 발생한다면 메모제이션을 고려하자.

출처: 프로그래머스 코딩 테스트 연습, 
https://school.programmers.co.kr/learn/challenges