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

package org.example.알고리즘.정수삼각형;

import java.util.Arrays;

class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        
        System.out.println(solution.solution(new int[][]{
                {7},
                {3, 8},
                {8, 1, 0},
                {2, 7, 4, 4},
                {4, 5, 2, 6, 5},
        }));
    }
    
    public int solution(int[][] triangle) {
        
        int[][] dp = new int[triangle.length][triangle.length];
        
        dp[0][0] = triangle[0][0];
        
        for (int i = 1; i < triangle.length; i++) {
            dp[i][0] = dp[i - 1][0] + triangle[i][0];
            dp[i][i] = dp[i - 1][i - 1] + triangle[i][i];
            
            for (int j = 1; j < i; j++) {
                dp[i][j] = Math.max(dp[i - 1][j - 1], dp[i - 1][j]) + triangle[i][j];
            }
        }
        return Arrays.stream(dp[triangle.length - 1])
                .max()
                .getAsInt();
    }
}

• 단순히

• 점화식 유도로 해결가능한 문제임

하지만, 굳이 마지막 배열 인덱스에서 스트림을 돌아야할까?

라는 생각이 들었음

public int solution(int[][] triangle) {
        int maxValue = 0;
        
        int[][] dp = new int[triangle.length][triangle.length];
        
        dp[0][0] = triangle[0][0];
        for (int i = 1; i < triangle.length; i++) {
            dp[i][0] = dp[i - 1][0] + triangle[i][0];
            maxValue = Math.max(maxValue, dp[i][0]);
            
            dp[i][i] = dp[i - 1][i - 1] + triangle[i][i];
            maxValue = Math.max(maxValue, dp[i][i]);
            
            for (int j = 1; j < i; j++) {
                dp[i][j] = Math.max(dp[i - 1][j - 1], dp[i - 1][j]) + triangle[i][j];
                maxValue = Math.max(maxValue, dp[i][j]);
            }
        }
        return maxValue;
    }
}

• 더럽긴한데 이런식으로 해도 실행시간에는 거의 차이가 없었음..
  • 마지막에 스트림을 돌지 않기 때문에, 조금은 더 빠르지 않을 까 싶었음

• 아마

  

  • 마지막 삼각형의 원소의 최대 크기가 500.. 이라서 차이가 없는거같음.

Uploaded by N2T