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

프로그래머스 level3 정수 삼각형

 

소요시간 : 53분

 

dp 항상 어려워했었고 푸는데 엄청 오래걸렸다 ㅋㅋㅋㅋㅋㅋ

그냥 dfs로 하니 시간초과나서 한참 고민했다

 

최댓값을 찾으려면 결국 밑에 있는 값이 중요하니 세로(i)를 N-1부터 시작해서 1까지,

가로(j)를 0~길이-1까지 양쪽 대각선 위로 다 더해보고 최댓값을 갱신했다.

결국 아래에서 꼭대기까지 최대합이 triangle[0][0] 에 저장되게 된다.

 

class Solution {
  int MAX = 0;
  int N;
  public int solution(int[][] triangle) {
    N = triangle.length;
    if(N == 1) return triangle[0][0];

    int[] arr;
    for (int i = N-1; i >= 1; i--) {
      arr = new int[triangle[i-1].length];
      for (int j = 0; j < triangle[i].length; j++) {
        if(j-1 >= 0) {
			arr[j-1] = Math.max(arr[j-1], triangle[i][j] + triangle[i-1][j-1]);
        }
        if(j < triangle[i-1].length) {
			arr[j] = Math.max(arr[j], triangle[i][j] + triangle[i-1][j]);
        }
      }
      for (int j = 0; j < arr.length; j++) {
      	triangle[i-1][j] = arr[j];
      }
    }

    return triangle[0][0];
  }
}