[programmers] 정수 삼각형 - Java

정수 삼각형 문제에서는 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾는다. 이를 위해 삼각형의 아래부터 위로 순회하며 각 노드의 오른쪽, 왼쪽 자식들의 값 중 최댓값을 구하고, 이를 부모의 값에 더해서 배열에 저장한다. 최종적으로 배열의 0번 인덱스의 0번째 값이 최댓값이 된다. 이 문제를 통해 동적 계획법의 기초를 이해할 수 있다.

DriedPollack

Apr 03, 2024

Contents

정수 삼각형 solution.java 핵심 키워드 결론!

정수 삼각형

문제 설명

위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다.

삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요.

제한사항

삼각형의 높이는 1 이상 500 이하입니다.

삼각형을 이루고 있는 숫자는 0 이상 9,999 이하의 정수입니다.

입출력 예

triangle	result
[[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]]	30

solution.java


class Solution {
    public static int solution(int[][] triangle) {
        int height = triangle.length;
        int[][] dp = new int[height][height];

        // 삼각형의 맨 아래 행 값으로 dp 배열을 채우기
        for (int i = 0; i < height; i++) {
            dp[height - 1][i] = triangle[height - 1][i];
        }

        // 아래에서 위로 삼각형 순회
        for (int i = height - 2; i >= 0; i--) {
            for (int j = 0; j <= i; j++) {
                // dp 배열의 각 위치에 대한 최댓값 계산
                dp[i][j] = triangle[i][j] + Math.max(dp[i + 1][j], dp[i + 1][j + 1]);
            }
        }

        // 최댓값 반환
        return dp[0][0];
    }
}