[LeetCode][JS] 120번 Triangle

⚡문제 유형

DP

 

📝문제

주어진 triangle을 위에서 아래로의 최소 경로 합계를 반환합니다 .

각 단계에 대해 아래 행의 인접한 번호로 이동할 수 있습니다.

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

-> 피라미드 구조로 내려오면서 i 또는 i+1로 이동해서 최솟값 구하는 문제

 

📘예시

Input: triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
Output: 11
Explanation: The triangle looks like:
   2		// 2
  3 4		// 최솟값을 만들기 위해 2에서 갈 수 있는 다음 행 (3,4) -> 3
 6 5 7		// 최솟값을 만들기 위해 3에서 갈 수 있는 다음 행 (6,5) -> 5
4 1 8 3    	// 최솟값을 만들기 위해 5에서 갈 수 있는 다음 행 (1,8) -> 5
The minimum path sum from top to bottom is 2 + 3 + 5 + 1 = 11 (underlined above).

Input: triangle = [[-10]] // 하나밖에 없으니 결과는 -10
Output: -10

 

📗풀이

💡시작은 뒤에서 두번째 행부터

먼저, 위과 같은 triangle이 있다고 하자. 

시작은 노란 화살표가 있는 triangle의 맨 마지막의 두번째인 곳에서 시작을 한다. 

 

두번째 줄에 있는 2와 3에 각각 인접한 다음 행의 인덱스 번호 중 최솟값을 더해준다. 

더해주면 2와 3은 각각 6과 8이 된다.

2번째 행에서 모든 연산을 끝내고 첫번째 행으로 간다. 

1에서 접근할 수 있는 6과 8 중 최솟값을 더해준다.

📕코드

var minimumTotal = function (triangle) {
  for (let i = triangle.length - 2; i >= 0; i--) {
    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];
};