(코테) 프로그래머스_정수 삼각형 * dp ,인플레이스 dp

 

문제 링크

 

https://school.programmers.co.kr/learn/courses/30/lessons/43105?language=java

 

 

 

1. 내가 처음 제출한 답   dp 배열 생성

class Solution {
    public int solution(int[][] triangle) {
        int answer = 0;
        int[][] dp = new int[triangle.length][triangle.length];

        for(int i=0;i<triangle.length;i++){            
            for(int j=0;j<i+1;j++){
                //원본 복제
                dp[i][j] = triangle[i][j];                
            }
        }
        
        for(int i=0;i<triangle.length-1;i++){           
            for(int j=0;j<i+1;j++){                                
                //int tmp = dp[i][j];
                
                int first = dp[i][j] + triangle[i+1][j];
                int second = dp[i][j] + triangle[i+1][j+1];
                
                if(first>dp[i+1][j])  dp[i+1][j] =first;
                if(second>dp[i+1][j+1])  dp[i+1][j+1] =second;
                
            }
        }
        int max=0;
        
        for(int next : dp[triangle.length-1]){
            max = Math.max(max,next);
        }
        
        return max;
    }
}

 

 

 

 

2. dp 배열 없이  인플레이스 dp 방법 

class Solution {
    public int solution(int[][] triangle) {
        // 맨 아래에서 위로 올라가며 DP를 수행합니다.
        for (int i = triangle.length - 2; i >= 0; i--) {
            for (int j = 0; j <= i; j++) {
                // 현재 위치의 값에 아래 두 자식 중 더 큰 값을 더해 갱신합니다.
                triangle[i][j] += Math.max(triangle[i + 1][j], triangle[i + 1][j + 1]);
            }
        }

        // 최종적으로 맨 위(triangle[0][0])에 최대 합이 저장됩니다.
        return triangle[0][0];
    }
}

 

 

회고

1. 최초 제출한 답은 피라미드 꼭대기에서 아래로 내려가는 방식으로 설계

 

2. 인플레이스 dp 방식은  역피라미드로 밑에서부터 가지의 높은 자식을 내 노드?와 더하는 식으로 가장 꼭대기가 가장 큰 값이 되도록 만드는 방법    dp 배열 생성x