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

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

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

풀이 방법 (DP)

삼각형의 꼭대기에서 가장 최하단까지 내려오면서 각 구역의 숫자를 더해 가장 큰 값이 되는 것을 구하는 문제이다.

 

각 층별로 현재 위치의 최댓값을 정하면서 내려왔다.

 

가장 좌측과 우측은 내려 올 수 있는 길이 한가지여서 예외처리를 하였으며, 아닌 경우 올 수 있는 길은 2가지 경우이다.

 

2가지경우 중 큰 값에 현재 값을 더하였다.

 

 

소스코드(Javascript)

function solution(triangle) {
    var answer = 0;
    var dp = new Array(triangle.length);
    dp[0] = new Array(1);
    dp[0][0] = triangle[0][0];
    answer = dp[0][0];
    for (var i = 1; i < triangle.length; i++) {
        dp[i] = new Array(i + 1);
        for (var j = 0; j < triangle[i].length; j++) {
            if (j == 0) {
                dp[i][j] = dp[i - 1][0] + triangle[i][j];
            }
            else if (j == triangle[i].length - 1) {
                dp[i][j] = dp[i - 1][triangle[i - 1].length - 1] + triangle[i][j];
            }
            else {
                dp[i][j] = dp[i - 1][j - 1] > dp[i - 1][j] ? dp[i - 1][j - 1] + triangle[i][j] : dp[i - 1][j] + triangle[i][j];
            }
            if (answer < dp[i][j]) {
                answer = dp[i][j];
            }
        }
    }
    return answer;
}