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

문제 설명 보기

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

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

 

바이너리 트리를 탐색하며 가장 큰 숫자의 branch를 찾는 문제 같지만 그런식으로 순회하면 무조건 time-out이 되도록 설계된 문제다.

자식 Node로 탐색하는 방법 중 가장 가중치가 크도록 탐색하는 방법은 두개의 부모 노드 중 가중치가 더 큰 노드를 통해 탐색하는 법이므로, 그를 통해 문제를 해결했다.

가중치가 있는 길찾기를 한다고 생각하면 편하다.

import java.util.Arrays;
import java.util.Collections;
import java.util.stream.Collectors;

class Solution {
    public int solution(int[][] triangle) {
        if(triangle.length == 1) return triangle[0][0];

        for(int row = 1; row < triangle.length; row++){
            for(int col = 0; col < triangle[row].length; col++){
                int left = 0;
                int right = 0;
                if(col != 0){
                    left = triangle[row-1][col-1];
                }
                if(col != triangle[row].length-1){
                    right = triangle[row-1][col];
                }
                triangle[row][col] += Math.max(left, right);
            }
        }
        return Collections.max(Arrays.stream(triangle[triangle.length-1]).boxed().collect(Collectors.toList()));
    }
}