120. Triangle

문제 링크: https://leetcode.com/problems/triangle/
난이도: Medium

 

Given a triangle array, return the minimum path sum from top to bottom.

For each step, you may move to an adjacent number of the row below. More formally, if you are on index i on the current row, you may move to either index i or index i + 1 on the next row.

 

삼각형 배열이 주어지면 위에서 아래로 최소 경로 합계를 반환합니다.
각 단계에 대해 아래 행의 인접한 번호로 이동할 수 있습니다. 

보다 공식적으로, 현재 행의 인덱스 i에 있는 경우 다음 행의 인덱스 i 또는 인덱스 i + 1로 이동할 수 있습니다.

 

Example 1:

Input: triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
Output: 11
Explanation: The triangle looks like:
   2
  3 4
 6 5 7
4 1 8 3
The minimum path sum from top to bottom is 2 + 3 + 5 + 1 = 11 (underlined above).

Example 2:

Input: triangle = [[-10]]
Output: -10

 

Constraints:

• 1 <= triangle.length <= 200
• triangle[0].length == 1
• triangle[i].length == triangle[i - 1].length + 1
• -104 <= triangle[i][j] <= 104

Related Topics: Array, Dynamic Programming

---

문제풀이

 

2
3 4
6 5 7
4 1 8 3

 

위와 같은 삼각형 형태의 배열이 있으면 삼각형 제일 위에서부터(top to bottom)

그 아래줄에 있는 인접 인덱스(기존 값의 인덱스와 동일하거나( i ) 그 인덱스보다 1 큰( i+1 ) 인덱스로 이동하되,

경로의 최소 합계(minimum path sum)이므로 두 인덱스 중에서 더 작은 값(Math.min)으로 이동하도록 해야 한다.

두 index 값이 필요하니 for문 2개를 중첩하고 경로의 최소 해를 계산하는 함수를 구성한다.

/**
 * @param {number[][]} triangle
 * @return {number}
 */
var minimumTotal = function(triangle) {
    //삼각형 배열에서 minimum path sum
    //아래줄 인접 번호로 이동-index i 또는 i+1(최소 해니까 그중에서 더 작은 숫자로 가는 거임)
    //Dynamic Programming 동적 프로그래밍-재귀 or 반복문
    
    //1
    for (let i=0;i<triangle.length;i++){
    	for (let j=0;j<=i;j++){
        	//인접 index로만 이동하니까 i보다 작거나 같으면 됨
            if (j==0){
                triangle[i][j] += triangle[i-1][j];
            } else if (j == i) {
                triangle[i][j] += triangle[i-1][j-1];
            } else {
                triangle[i][j] += Math.min(triangle[i-1][j],triangle[i-1][j-1]);
            }
        }
    }
    return Math.min(...triangle[triangle.length-1]);
    
    //2
    for (let i = triangle.length-2; i >= 0; i--)
        //실질적인 알고리즘 시작이 2번째 줄부터라서/음수 되는거 방지
        for (let j = 0; j < triangle[i].length; j++)
            triangle[i][j] += Math.min(triangle[i+1][j], triangle[i+1][j+1]);
    return triangle[0][0];
};

Discussion에 좋은 설명 영상이 있어서 같이 올려본다.

https://www.youtube.com/watch?v=YzGQ90BF4eo