[DP] 정수 삼각형

https://school.programmers.co.kr/learn/courses/30/lessons/43105?language=javascript 

프로그래머스

 

 

 

 

첫 풀이

function solution(triangle) {
    var answer = 0;
    let memo = [7];
    for (let r = 1; r < triangle.length; r++) {
        const newMemo = [];
        for (let c = 0; c < triangle[r].length; c++) {
            const currValue = triangle[r][c];
            // 맨 처음이거나 마지막 인덱스
            const before = c-1 < 0 ? 0 : memo[c-1];
            const now = memo[c] || 0;
            newMemo[c] = Math.max(before, now) + currValue;
        }
        memo = newMemo;
    }
    return memo.sort((a, b) => b-a)[0];
}

로직

현재위치까지 오는데 최댓값을 구하는 공식

현재위치까지 최대값 = arr[이전의 항][이전 열]와 arr[이전의 항][현재 열] 중 최댓값 + 현재위치의 값
arr[r][c] = Math(arr[r-1][c-1], arr[r-1][c])

 

이 전 행까지 메모제이션을 해온다

memo = [
  [ 7 ],
  [ 10, 15 ],
  [ 18, 16, 15 ],
  [ 20, 25, 20, 19 ],
  [ 24, 30, 27, 26, 24 ]
]

 

첫열과 마지막 열은 arr[][]값이 없으므로  (undefined || 0)로 계산

function solution(triangle) {
    for (let i = 1; i < triangle.length; i++) {
        for (let j = 0; j < triangle[i].length; j++) {
            triangle[i][j] += Math.max(triangle[i-1][j-1] || 0, triangle[i-1][j] || 0);
        }
    }
    // return triangle[triangle.length-1].sort((a, b) => b-a)[0];
    return Math.max(...triangle[triangle.length-1]);
}

 

효율성이 통과가 안 됐다. 왜?

 

for 루프에서 i++, j++를 i +=1, j +=1로 바꿔주니 통과.. 왜???

 

function solution(triangle) {
    for (let i = 1; i < triangle.length; i +=1) {
        for (let j = 0; j < triangle[i].length; j+=1) {
            triangle[i][j] += Math.max(triangle[i-1][j-1] || 0, triangle[i-1][j] || 0);
        }
    }
    // return triangle[triangle.length-1].sort((a, b) => b-a)[0];
    return Math.max(...triangle[triangle.length-1]);
}