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

문제 설명

1. 삼각형이 주어진다.

2. 맨 아래까지 삼각형을 하나씩 더해가면서 그 최대값을 구한다.

3. 맨 아래줄에서 최대값을 구해주면 된다.

풀이 과정

 1. 간단한 DP 문제이다....이게 왜 level3일까??

 2. 각 삼각형 위치에서 가장 큰 합을 구하는 배열을 만들어 준다.

 3. 맨 왼쪽은 무조건 다 왼쪽으로 이동해야 하므로 0, 0부분은 싹다 현재 삼각형 크기와 위의 크기를 더해주면 된다.

7 - 3 - 8 - 2 - 4 (이렇게 왼쪽으로 가는거는 쭉쭉 더해주면 될것이다. 다른 방법은 없다.)

 

  4. n번째 위치의 최대값은 그보다 윗 칸의 왼쪽에 있는 값, 오른쪽에 있는 값중 큰거를 구하면 된다.

  5. 이제 맨 아래 위치의 값들 중 최대값을 return하면 된다.

 

코드

class Solution {
    public int solution(int[][] triangle) {
        int answer = 0;
        int wholeLength = triangle.length;  // 삼각형 크기 
        
        int sum[][] = new int[wholeLength][wholeLength];	// 결과가 저장될 sum
        sum[0][0] = triangle[0][0]; // 맨위값의 합은 당연히 맨 위 삼각형
        for(int i=1; i<wholeLength; i++)
            sum[i][0] = sum[i-1][0] + triangle[i][0]; // 삼각형의 왼쪽 위치의 최대합은 그 위 + 해당 삼각형 값
        
        for(int i=1; i<wholeLength; i++){
            for(int j=1; j<=i; j++){  // 다른곳의 값들은 해당 위치 기준 위에서 더 큰값 + 현재 삼각형 값
                sum[i][j] = triangle[i][j] + Math.max(sum[i-1][j], sum[i-1][j-1]);
            }
        }
        
        for(int i=0; i<wholeLength; i++)		// 최대값 구하기
            answer = Math.max(answer, sum[wholeLength-1][i]);
        
        return answer;	// 답 출력
    }
}