문제

위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다.

삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요.

제한 사항

• 삼각형의 높이는 1 이상 500 이하입니다.
• 삼각형을 이루고 있는 숫자는 0 이상 9,999 이하의 정수입니다.

풀이

아이디어

• 처음 레벨에서 끝 레벨까지 가면서 거쳐간 경로의 수들을 계속 누적해서 더한다 + 움직일 수 있는 경로를 아랫방향으로만 잡아준다 + 어쨌든 뭔가를 기록하면서 마지막에 최댓값을 구한다? => DP
• 저 피라미드 모양 그대로 메모이제이션용 배열(cache)를 만들어야겠다고 생각. (주의: 생각없이 만들었다가는 얕은 복사가 되어서 원본 triangle 배열도 바뀌어버리는 수가 있으니 JSON.parse와 JSON.stringify를 이용해서 반드시 깊은 복사가 되도록 하자.)
• cache 배열은 여태까지 해당 위치까지 오기까지의 최대 누적합이 기록되어 있는 배열로 정의한다.
• [row, col]의 위치까지 오는 데 누적합의 최대는 [row, col]에 오기 전까지의 누적합 중 최댓값과 triangle에서의 같은 위치의 값을 더한 값이다.
• 만약 col === 0이라면 무조건 바로 윗줄의 첫번째 값만 영향을 줄 수 있다.
• 만약 col === 끝줄이라면 무조건 바로 윗줄의 마지막 값만 영향을 줄 수 있다.
• 위의 두 케이스가 아니라면 바로 윗줄의 같은 인덱스의 값 또는 바로 윗줄의 현재 col값 - 1번째 값이 영향을 줄 수 있다. 따라서, 둘 중에 최댓값을 골라야 한다.

코드

function solution(triangle) {
    const cache = JSON.parse(JSON.stringify(triangle));
    cache.forEach(arr => {
        for(let i=0; i < arr.length; i++) arr[i] = 0;
    });
    cache[0][0] = triangle[0][0];
    
    for(let row=1; row<triangle.length; row++) {
        for(let col=0; col<triangle[row].length; col++) {
            if(col === 0) cache[row][col] = triangle[row][col] + cache[row-1][col];
            else if(col === triangle[row].length - 1) cache[row][col] = triangle[row][col] + cache[row-1][col-1];
            else cache[row][col] = triangle[row][col] + Math.max(cache[row-1][col-1], cache[row-1][col]);
        }
    }
    
    const resultRow = cache[triangle.length -1].sort((a, b) => b - a);
    return resultRow[0]
}

참고

맨 마지막 값을 리턴할 때 그냥 Math.max(...cache[triangle.length-1])을 했었는데 1번 효율성 테스트를 탈락했다. 그래서 위와 같이 내림차순 정렬 후 첫번째 원소를 반환하는 방식으로 바꿨더니 통과했다.