[프로그래머스/Java] 정수 삼각형

문제

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

---

문제 파악

• 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중 숫자의 합이 가장 큰 경우를 찾는 문제
• 이동 시 아래층의 바로 아래, 또는 바로 오른쪽 숫자로만 이동할 수 있음
• 삼각형의 높이가 500까지 이기 때문에 단순 dfs로 풀 수 X → DP 알고리즘 사용

---

접근 방법

• 삼각형 배열과 같은 크기의 dp 배열을 생성하여 각 위치의 최대 경로 합을 저장
• 삼각형 배열을 순차적으로 탐색하며 각 위치에서 위의 두 경로( 바로 위, 왼쪽 대각선) 중 더 큰 값을 선택하여 현재 위치에 더함
• 마지막 행에 있는 값들 중 가장 큰 값을 찾아 반환 → 그 값이 삼각형을 내려오는 경로 중 최대 합임

---

코드 구현

class Solution {
    public int solution(int[][] triangle) {
        int answer = 0;
        int h = triangle.length;
        int[][] dp = new int[h][h];
        
        // 삼각형의 첫번째 원소를 dp 배열에 초기화
        dp[0][0] = triangle[0][0];
        
        // 삼각형의 가장 왼쪽 원소들을 초기화
        for(int i = 1; i < h; i++)
            dp[i][0] = dp[i - 1][0] + triangle[i][0];
        
        // 나머지 경로에 대한 최댓값 계산
        for(int i = 1; i < h; i++){
            for(int j = 1; j <= i; j++) // 삼각형 형태의 배열 구조로 i까지 반복
                // 바로 위와 그 왼쪽 중 큰 값을 선택하여 현재 위치에 더함
                dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - 1]) + triangle[i][j];
        }
        
        for(int i = 0; i < h; i++)
            answer = Math.max(dp[h - 1][i], answer);
        
        return answer;
    }
}