[프로그래머스/Lv.3] 정수 삼각형 - Java

문제

https://school.programmers.co.kr/learn/courses/30/lessons/43105

프로그래머스

 

 

 

리뷰

DP(동적계획법) 문제이다. 직전 단계까지의 계산을 따로 저장해놓고 현 단계를 계산할 때 이를 사용해야 한다.

풀이

주어진 triangle과 똑같은 형태의 이차원배열 memo를 생성했다. 그리고 맨 위 숫자부터 차례로 내려왔을 때 triangle의 각 값에 도달하기까지 만들어지는 최대값을 memo에 기록한다.

 

이때 맨 왼쪽 값들과 맨 오른쪽 값들은 바로 위에 있는 값을 계속 누적해서 합해주면 된다.

각 줄에서 인덱스가 0인 원소들을 계산하는 법

 

다만 문제는 중간에 있는 숫자들이다. 중간 숫자에 대한 memo 값은 해당 숫자로 올 수 있는 직전 단계를 기반으로 구한다.

 

memo에서 i번째 줄의 j번째 값을 구한다고 치자. i번째 줄의 j번째 숫자로 올 수 있는 직전 단계 숫자는 i-1번째 줄의 j-1번째 값과 j번째 값이다.

각 row에서 인덱스가 0도 아니고 row-1도 아닌 위치의 값을 계산하는 법

따라서 memo[i][j] = (memo[i-1][j-1]과 memo[i-1][j] 중 더 큰 값) + triangle[i][j] 라고 볼 수 있다.

이후 마지막 줄에서 최대값을 찾아 반환하면 된다.

 

 

코드

import java.util.*;

class Solution {

    int totalDepth;
    int answer = 0;
    int[][] memo;

    public int solution(int[][] triangle) {
        int answer = 0;

        totalDepth = triangle.length;

        memo = new int[totalDepth][];
        for(int row = 0; row < totalDepth;row++){
            int len = triangle[row].length;
            memo[row] = new int[len];
            Arrays.fill(memo[row], -1);
        }

        memo[0][0] = triangle[0][0];        
        for(int depth = 1; depth < totalDepth; depth++){
            memo[depth][0] = memo[depth-1][0]+triangle[depth][0];
            for(int i = 1;i<depth;i++) {
                memo[depth][i] = (memo[depth-1][i-1] > memo[depth-1][i])?memo[depth-1][i-1] : memo[depth-1][i];
                memo[depth][i]+=triangle[depth][i];
            }
            memo[depth][depth] = memo[depth-1][depth-1]+triangle[depth][depth];
        }

        answer = Arrays.stream(memo[totalDepth-1]).max().getAsInt();

        return answer;
    }

}