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

링크 : https://school.programmers.co.kr/learn/courses/30/lessons/43105#qna

프로그래머스

---

문제 풀이

위에서부터 아래로 내려가며 각 위치까지 가는 최대값을 구해주며 탐색하였다.

 

DP[h][n] : h높이의 삼각형에서 n까지 가는데 최대값 이라고 가정하였을때,

 

D[1][0] = 1층 삼각형의 0번째 index까지 가는 최대값 -> 7 + 3 = 10

D[1][1] = 1층 삼각형의 1번째 index까지 가는 최대값 -> 7 + 8 = 15

...

* 높이는 0부터 시작

 

이때, D[3][2] = Math.max(D[2][1], D[2][2]) + triangle[3][2]이 되는 것을 확인할 수 있다.

이를 활용해 점화식을 세우면 아래와 같다.

// n이 0일 경우
dp[h][n] = dp[h-1][0] + triangle[h][n];

// n이 0이 아닐 경우
dp[h][n] = Math.max(dp[h-1][n-1], dp[h-1][n]) + triangle[h][n];

 

마지막 층까지 계산해준 후, 마지막 층의 값들 중 최대값을 리턴해준다.

 

 

 

import java.util.*;

class Solution {
    public int solution(int[][] triangle) {
        int answer = 0;
        int[][] dp = new int[triangle.length][triangle.length];
        
        // 점화식
        // dp[h][n] : h높이의 삼각형에서 n까지 가는데 최대값
        dp[0][0] = triangle[0][0];

        for(int i=1; i<triangle.length; i++) {
			for(int j=0; j<=i; j++) {
				if(j==0) {
					dp[i][j] = dp[i-1][0] + triangle[i][j];
				} else {
					dp[i][j] = Math.max(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j];
				}
			}
		}
        
        for(int i=0; i<triangle.length; i++) {
            answer = Math.max(answer, dp[triangle.length-1][i]);
        }
        
        return answer;
    }
}