[JAVA/프로그래머스] 동적계획법(Dynamic Programming)_정수 삼각형

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
import java.util.*;
/**
 *
 * @author HEESOO
 *
 */
 class Solution {
     public int solution(int[][] triangle) {
         int answer = 0;
         int sum[][]=new int[triangle.length][triangle.length];//합을 저장할 배열
         sum[0][0]=triangle[0][0];
         for(int i=1;i<triangle.length;i++){//가장 왼쪽과 오른쪽은 다음 위치가 지정되어있음
             sum[i][0]=sum[i-1][0]+triangle[i][0];
             sum[i][i]=sum[i-1][i-1]+triangle[i][i];
         }

         for(int i=2;i<triangle.length;i++){//현재 위치로 올 수 있는 이전 줄 대각선 왼쪽 오른쪽 중 최댓값을 선택
             for(int j=1;j<i;j++){
                 sum[i][j]=Math.max(sum[i-1][j-1],sum[i-1][j])+triangle[i][j];
             }
         }
         int max=sum[sum.length-1][0];
         for(int j=1;j<sum.length;j++){//마지막 행에서 최댓값을 선택
             max=Math.max(max, sum[sum.length-1][j]);
         }
         answer=max;
         return answer;
     }
 }