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

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

programmers.co.kr/learn/courses/30/lessons/43105

코딩테스트 연습 - 정수 삼각형

풀이

DP문제 치고 쉬운 DP문제여서 어렵지 않게 접근했다! 위치별로 누적 값을 저장하여주기 위해 dp를 2차원 배열로 만들어 주었다. 그리고 마지막에 배열의 마지막줄에서 최댓값을 찾아 반환해 주었다. 

 

우선 문제의 예제를 분석해 보았다.

7
3	8
8	1	0
2	7	4	4
4	5	2	6	5

예제에 따르면 매개변수인 triangle은 이러한 형태로  전달된다.

 

이때 각 항목별로 값을 계산해 나가는 과정을 써보았다.

dp[0][0] = triangle[0][0]

dp[1][0] = dp[0][0] + triangle[1][0]

dp[1][1] = dp[0][0] + triangle[1][1]

dp[2][1] = dp[1][1] + triangle[2][1]

dp[2][2] = (dp[1][0], dp[1][1]중 최댓값) + triangle[2][2]

과정을 보면 노란색으로 칠해진 부분 즉, 맨 왼쪽 요소는 항상 바로 위의 값을 더해주고, 맨 오른쪽 요소는 왼쪽 대각선 위의 값을 더해준다.

나머지는 모두 왼쪽 대각선 위의 값과 바로 위쪽 값 중에 최댓값을 찾아 더해준다.

 

끝이다. 이걸 그대로 식에 옮겨주면 된다.

코드

import java.util.*;
 
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++) {
            for(int j = 0; j < triangle[i].length; j++) {
                if(j == 0) dp[i][j] = dp[i - 1][j] + triangle[i][j];
                else if(j == triangle[i].length - 1) dp[i][j] = dp[i - 1][j - 1] + triangle[i][j];
                else dp[i][j] = Math.max(dp[i - 1][j - 1], dp[i - 1][j]) + triangle[i][j];
            }
        }
        
        int max = 0;
        int last = triangle.length - 1;
        for(int i = 0; i < triangle[last].length; i++) {
            max = Math.max(max, dp[last][i]);
        }
        return max;
    }
}