Leetcode Java Triangle

문제

Link

코드

class Solution {

  public int minimumTotal(List<List<Integer>> triangle) {
    int[] dp = new int[triangle.size() + 1];
    for (int i = triangle.size() - 1; i >= 0; i--) {
      List<Integer> row = triangle.get(i);
      for (int j = 0; j < row.size(); j++) {
        dp[j] = Math.min(dp[j], dp[j + 1]) + row.get(j);
      }
    }
    return dp[0];
  }

}

결과

Link

설명

1. 주어진 삼각형의 값들을 저장한 List인 triangle을 이용하여 위에서 아래로 이동하며 만들어진 합이 최소인 값을 찾는 문제이다.
   • 단, 이동 할 때 자신의 위치와 자신의 위치 + 1인 위치로 이동이 가능하다.
   • 예를 들어 아래의 삼각형에서 현재 위치가 2인 경우, 5와 4로만 이동이 가능하다.

   1
  2 3
 5 4 6
8 9 7 10

1. 최소 값을 저장하기 위한 배열 dp를 주어진 triangle의 크기보다 1 크게 정의한다.

2. 반복문을 이용하여 bottom-up으로 최소가 되는 합을 구한다.
   • 반복적인 메모리 소모를 지양하기 위하여 triangle의 i번째 row를 지역 변수로 정의한다.
   • 또 다시 반복문을 이용하여 row의 크기만큼 반복하여 dp의 값을 넣어준다.
     • dp[i]에 dp[j]와 dp[$j + 1$]의 값 중 최소 값과 row의 j번째 값의 합을 넣어준다.
     • bottom-up으로 삼각형의 밑에서 위로 역순으로 탐색을 하므로, 각 값의 최소 값을 역행하여 수행하면 dp[0]에는 가장 최소가 되는 합계만 남아있게 된다.
     • 예를 들어 위의 삼각형으로 예를 들면, 1 -> 2 -> 4 -> 7의 합인 14가 되기 위해서 위의 내용을 반복하여 만들어보면 [13, 11, 13] -> [13, 14] -> [14]가 완성된다.
3. 반복문이 완료되면 초기화된 dp의 0번째 값을 넣어준다.

소스

Sample Code는 여기에서 확인 가능합니다.