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

🫡 문제

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

🫡 코드

class Solution {
    public int solution(int[][] triangle) {        
        int answer = 0;
        int[][] dp = new int[triangle.length][triangle.length];
        
        //맨 꼭대기 dp 값 
        dp[0][0] = triangle[0][0];

        for(int i=1; i<triangle.length; i++){
            //첫번째 dp 값
            dp[i][0] = dp[i-1][0] + triangle[i][0];

            //중간 dp값
            for(int j=1; j<=i; j++){
                dp[i][j] = 	Math.max(dp[i-1][j-1],dp[i-1][j]) + triangle[i][j];
            }

            //마지막 dp값
            dp[i][i] = dp[i-1][i-1] + triangle[i][i];
        }
        
        //마지막 줄 dp 값들 중에서 최대값 저장
        for(int i=0; i<triangle.length; i++){
            answer = Math.max(answer, dp[triangle.length-1][i]);
        }

        return answer;
    }
}

🫡 풀이

DP(Dynamic Programming; 동적 계획법)

이전에 연산한 결과 중 큰 값을 배열에 담아 중복 연산을 줄이기 위해 사용하는 방법

👀이해하기 쉽게 각 배열에 들어갈 값을 하나하나 다 적어 보았다

---

triangle 배열

dp 배열

1. triangle 배열과 동일한 크기의 배열(dp)을 생성한다.
2. dp[0][0]에 들어갈 값은 더해준 값이 아니기 때문에 그대로 저장한다.
3. 첫번째 dp값 [1][0], [2][0], [3][0] 과 같은 값들은 [i-1][0]+[i][0] 연산만 해주면 된다.
4. 중간 dp값들은 [i-1][j-1]+[i][j] or [i-1][j]+[i][j] 연산 중 최댓값을 저장해주면 된다.
5. 마지막 dp값은 [i-1][i-1] + [i][i] 연산을 해주면 된다.
6. 위의 연산이 끝나면 dp배열의 마지막 줄에는 연산한 값 중 큰 값들이 저장되어 있을 텐데
   이 중에서 가장 최댓값을 출력하면 된다.
   👉 최댓값 출력 시에는 Math.max 이용

📢 중복 연산을 줄이기 위해서 값을 저장하기 때문에 triangle 배열과 dp 배열의 연산을 적절히 사용해야한다.