프로그래머스 정수 삼각형

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

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

 

제출 날짜: 2021년 9월 22일 수요일

 

 

접근 방법

두 번째 줄부터 마지막 줄까지 이전 줄의 왼쪽 또는 오른쪽의 최댓값을 반복해서 더한다. 이때 맨 왼쪽과 맨 오른쪽은 각각 이전 줄의 왼쪽과 오른쪽 하나씩 그대로 가져와 더한다.

마지막 줄에서 최댓값을 답으로 출력한다.

 

 

 

생각

최댓값을 for문을 사용해서 구했는데, 다른 정답 풀이를 보니 한 줄에 끝내는 것이 있어 따라해봤다.

 

 

 

코드

import java.util.Arrays;

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

        for (int i = 1; i < triangle.length; i++) {
            for (int j = 0; j < triangle[i].length; j++) {
                if (j == 0) { // 제일 왼쪽에 있다면 그대로
                    triangle[i][j] += triangle[i - 1][j];
                } else if (j == triangle[i].length - 1) { // 제일 오른쪽에 있다면 그대로
                    triangle[i][j] += triangle[i - 1][j - 1];
                } else { // 그외는 윗줄의 왼쪽과 오른쪽 중 더 큰 값 가지기
                    triangle[i][j] += Math.max(triangle[i - 1][j - 1], triangle[i - 1][j]);
                }
            }
        }

        // 최댓값
        // for (int j = 0; j < triangle[triangle.length - 1].length; j++) {
        //     answer = Math.max(answer, triangle[triangle.length - 1][j]);
        // }
        answer = Arrays.stream(triangle[triangle.length - 1]).max().getAsInt();

        return answer;
    }
}