프로그래머스 Lv3_정수 삼각형_Java

https://school.programmers.co.kr/learn/courses/30/lessons/43105

프로그래머스

 

class Solution {
    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], dp[i-1][j-1]) + triangle[i][j];
            }
        }
          
        int answer = 0;
            
        for(int i = 0; i<triangle.length; i++) {
            if(answer < dp[triangle.length-1][i]) {
                answer = dp[triangle.length-1][i];
            }
        }
            
        return answer;
    }
}

 

 

풀이

- 삼각형 맨 왼쪽과 맨 오른쪽의 값을 구한다

- 우리가 생각해서 구해야 하는 부분은 삼각형의 중간 부분이다

- 문제에서 왼쪽 대각선 오른쪽 대각선으로 밖에 움직일 수 없다고 했으니 현재 위치 dp값은 현재 위치 값 + 왼쪽 대각선 위 dp값 과 오른쪽 대각선 위 dp값을 더해보고 비교해서 큰 값이 현재 위치의 dp값으로 정하면 된다.

 

 

회고

- dp가 정말 생각나지 않았다

- 프로그래머스 Lv3 쉽지않다

- 꾸준히 풀어보자