[프로그래머스] 정수 삼각형 (DP)

문제 소개

풀었던 정수 삼각형 - 프로그래머스 문제를 정리합니다.
이 문제는 삼각형 형태로 주어진 숫자들 중 꼭대기에서 바닥까지 이동하면서 만들 수 있는 최대 합을 구하는 문제입니다.

문제 링크: 정수 삼각형 - 프로그래머스

---

문제 접근 방식

이 문제는 다음과 같은 방식으로 접근했습니다:

 

1. 상단부터 차례대로 누적합을 계산하는 DP 방식 선택
2. 현재 위치로 오는 경로는 왼쪽 대각선 위 또는 오른쪽 대각선 위 두 가지뿐
3. 이전 줄의 결과를 활용해 누적합을 바로 갱신하며 아래로 내려감
4. 마지막 줄에서 최댓값을 선택하면 정답

 

---

해결 과정 및 코드

핵심 아이디어

1. 각 칸은 위의 두 경로 중 큰 값을 선택해 누적
   • 왼쪽 가장자리는 위에서 오는 한 방향만 가능 → triangle[i][0] += triangle[i-1][0]
   • 오른쪽 끝도 마찬가지로 하나만 존재 → triangle[i][i] += triangle[i-1][i-1]
   • 나머지 중간 위치는 양쪽 대각선 중 큰 값 선택
2. 이렇게 삼각형을 위에서 아래로 한 줄씩 갱신
3. 마지막 줄에서 가장 큰 수를 선택

코드

시간 복잡도 : O(N²)

import java.util.*;

class Solution {
    public int solution(int[][] triangle) {
        int h = triangle.length;

        // 두 번째 줄부터 갱신
        for (int i = 1; i < h; 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[h - 1]).max().getAsInt();
    }
}