[프로그래머스] 43105. 정수 삼각형

문제 링크

[프로그래머스] 43105. 정수 삼각형

풀이 과정

삼각형 위에서 아래로 진행하면서, 지나가는 경로의 합의 최대값을 memoization 배열에 담아둡니다.

memo 배열의 i, j 요소는 삼각형 높이 i에서 j 열의 요소를 채택했을 때 만들어지는 합의 최대값 을 의미합니다.

memo[0][0] 값은 triangle[0][0] 과 같습니다.

memo[0][0] = triangle[0][0];

이동은 배열을 기준으로 하단(↓) 및 우하단(↘︎) 할 수 있으므로, 삼각형 각 높이의 맨 왼쪽 요소와 맨 오른쪽 요소의 값은 이전 높이에서의 경로 누적 값 + 자기 자신 으로 정해져 있습니다. 예를 들어, 아래 그림에서 볼 수 있듯이, 두 번째 높이에서의 각 요소는 이전 높이에서의 최대 값인 7에 각 요소 3과 8을 더한 값인 10과 15가 됩니다.

if (j == 0) {
    memo[i][j] = memo[i - 1][j] + triangle[i][j];
} else if (j == i) {
    memo[i][j] = memo[i - 1][j - 1] + triangle[i][j];
}

맨 왼쪽과 맨 오른쪽 그 가운데에 위치한 요소들은 상단(↑) 및 좌상단(↖︎) 으로부터의 경로로 접근하므로, 해당 두 요소 중 큰 값에 자기 자신을 더합니다.

else {
    memo[i][j] = Math.max(memo[i - 1][j - 1], memo[i - 1][j]) + triangle[i][j];
}

위와 같은 방법으로 마지막 높이까지 요소를 채워 넣고, 마지막 높이에서의 최대값을 구해 반환하면 해결할 수 있습니다.

코드

public class Main {
    public static int solution(int[][] triangle) {
        int answer = 0;
        int[][] memo = new int[triangle.length][triangle.length];

        memo[0][0] = triangle[0][0];
        for (int i = 1; i < triangle.length; i++) {
            for (int j = 0; j < triangle[i].length; j++) {
                if (j == 0) {
                    memo[i][j] = memo[i - 1][j] + triangle[i][j];
                } else if (j == i) {
                    memo[i][j] = memo[i - 1][j - 1] + triangle[i][j];
                } else {
                    memo[i][j] = Math.max(memo[i - 1][j - 1], memo[i - 1][j]) + triangle[i][j];
                }
            }
        }

        for (int sum : memo[triangle.length - 1]) {
            answer = Math.max(answer, sum);
        }

        return answer;
    }

    public static void main(String[] args) {
        int[][] triangle = {{7}, {3, 8}, {8, 1, 0}, {2, 7, 4, 4}, {4, 5, 2, 6, 5}};

        solution(triangle);
    }
}