[알고리즘] 프로그래머스 정수 삼각형 :: 우유

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

프로그래머스

어렵지 않았지만, 배열 인덱스 범위를 잘못 지정해줘서 생각보다 오래걸렸던 문제다. 백준에도 비슷한 문제가 있었는데 다시 풀어봐도 헷갈렸던 문제..

triangle 2차원 배열의 인덱스를 초과 하지 않게 하기 위해서 왼쪽 가장자리와, 오른쪽 가장자리를 따로 초기화 해준다
DP[i][0] = DP[i - 1][0] + triangle[i][0];    // 왼쪽
DP[i][i] = DP[i - 1][i - 1] + triangle[i][i]; // 오른쪽

가운데가 핵심인데

이런 식으로 현재 위치에서 왼쪽 위에서 누적된 합과 오른쪽 위에서 누적된 합 중에 더 큰 값을 현재 값과 더해준다
DP[i][j] = Math.max(DP[i - 1][j], DP[i - 1][j - 1]) + triangle[i][j];

import java.util.*;

class Solution {

    public int solution(int[][] triangle) {
        int answer = 0;

        int len = triangle.length;

        int[][] DP = new int[len + 1][len + 1];

        DP[0][0] = triangle[0][0];

        for (int i = 1; i < len; i++) {
            // 맨 왼쪽
            DP[i][0] = DP[i - 1][0] + triangle[i][0];

            // 가운데
            for (int j = 1; j < i; j++)
                DP[i][j] = Math.max(DP[i - 1][j], DP[i - 1][j - 1]) + triangle[i][j];

            // 맨 오른쪽
            DP[i][i] = DP[i - 1][i - 1] + triangle[i][i];
        }

        for (int i = 0; i < len; i++)
            answer = Math.max(DP[len - 1][i], answer);

        return answer;
    }
}

성공적으로 통과!