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

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

프로그래머스

삼각형의 꼭대기에서 아래 왼쪽과 오른쪽으로 더하면서 내려가고, 그중 가장 큰 수를 찾는 문제

// 시간 초과 발생
class Solution {
    static int MAX = 0;
    public int solution(int[][] triangle) {
        tri(triangle, 0, 0, 0);
        return MAX;
    }

    public void tri(int[][] triangle, int max, int x, int y) {
        if (x == triangle.length) {
            MAX = Math.max(MAX, max);
            return;
        }
        tri(triangle, max + triangle[x][y], x+1, y);
        tri(triangle, max + triangle[x][y], x+1, y+1);
    }
}

위와 같이 재귀함수를 사용하면 답을 찾으려고 반복하는 과정에서 시간 초과가 발생한다

class Solution {
    public int solution(int[][] triangle) {
    	int answer = 0;
        for (int i = triangle.length - 1; i >= 0; i--) {
            for (int j = 0; j < triangle[i].length-1; j++) {
                triangle[i-1][j] += Math.max(triangle[i][j], triangle[i][j+1]);
            }
        }
        answer = triangle[0][0];
        return answer;
    }
}

삼각형의 맨 아래서 부터 왼쪽과 오른쪽 두 숫자 중 더 큰 수를 위쪽의 수와 더해서 마지막 꼭대기에서 가장 큰 수를 만드는 방법으로 문제를 풀었다.