[프로그래머스 / DP] 정수 삼각형 (java)

문제 설명

 

 

위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다.

삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요.

제한사항

• 삼각형의 높이는 1 이상 500 이하입니다.
• 삼각형을 이루고 있는 숫자는 0 이상 9,999 이하의 정수입니다.

입출력 예

triangleresult

[[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]]

30

 

[문제접근]

앞의 값을 누적시키고 맨 마지막에 도착한 값을 비교해서 max를 찾아야겠다는 생각. 

하지만 정삼각형의 최면에 걸려들어 어떻게 처리해야 할지 고민을 했다. 단순한 이차원 행렬일 뿐인데..

다른 분의 게시글을 참고하여 삼각형과 누적한 삼각형의 값을 어떻게 처리할지에 대한 힌트를 얻게 되었다. 

 

 

[java 코드]

class Solution {
    public int solution(int[][] triangle) {
        int answer = 0;
        int n = triangle.length;
        int[][] accTriangle = new int[n][n];
        int max=0;
        
        accTriangle[0][0] = triangle[0][0];
        for(int i=1; i<n; i++){
            accTriangle[i][0] = accTriangle[i-1][0] + triangle[i][0];
            accTriangle[i][i] = accTriangle[i-1][i-1] + triangle[i][i];
        }
        
        for(int i=2; i<n; i++){
            for(int j=1; j<i; j++){
                accTriangle[i][j] = Math.max(accTriangle[i-1][j-1], accTriangle[i-1][j]) + triangle[i][j];
            }
        }
        
        for(int i=0; i<n; i++){
            if(max < accTriangle[n-1][i])
                max = accTriangle[n-1][i];
        }
        answer = max;
        return answer;
    }
}

마지막에 max로 해놓고 return answer로 해놔서 계속 0떠서 코드 한참 째려봤는데....

answer = max를 안해줘서 그런거였음...

return max를 하던가..

 

[참고]

https://web2eye.tistory.com/163

프로그래머스 LEVEL 3 : 정수 삼각형 (DP)

[문제 링크]

https://programmers.co.kr/learn/courses/30/parts/12263

프로그래머스