프로그래머스 [Lv. 3] 정수 삼각형 {언어 : JavaScript}

문제 링크

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

프로그래머스

정답 코드

function solution(triangle) {
    const height = triangle.length;
    let dp = Array(height).fill().map((e, i) => Array(i+1).fill().map(() => 0));
    dp[0][0] = triangle[0][0];
    for (let idx = 1; idx < height; idx++) {
        const te = triangle[idx];
        const lenTe = te.length;
        
        te.forEach((e, jdx) => {
            // 왼쪽 인덱스
            const left = jdx ? jdx - 1 : -1;
            // 오른쪽 인덱스
            const right = jdx != lenTe - 1 ? jdx : -1;
            
            // 왼쪽 값
            const leftV = left != -1 ? dp[idx-1][left] + e : 0;
            // 오른쪽 값
            const rightV = right != -1 ? dp[idx-1][right] + e : 0;
            
            dp[idx][jdx] = Math.max(leftV, rightV)
        })
    }

    const answer = Math.max(...dp[height-1]);
    return answer;
}

풀이 방법

1. 0으로 채워진 triangle과 똑같은 높이의 배열을 만든다.
2. 꼭대기는 값을 채운다.
3. 1번 째 인덱스(2번 째 층)부터 바로 위층의 좌우 값과 비교한다.
   1. 현재 층의 jdx가 0인 경우 왼쪽 값은 없으므로 -1이며 leftV는 0이 된다.
   2. 현재 층의 jdx가 마지막 인덱스인 경우 오른쪽 값은 없으므로 -1이며 rightV는 0이 된다.
4. 좌우 값 중 큰 값을 dp[idx][jdx] 값에 넣어준다.
5. 마지막 층의 최대 값을 반환하면 끝

느낀점

• 바로 떠오르지 않는걸 보면 동적 계획법이 어려운 문제가 맞다.
• 지금은 풀었더라도 나중에는 못 풀 수도 있겠다는 생각이 들었다.
• 규칙을 찾고 규칙에 따라 어떻게 값을 저장할지 메모이제이션 방법에 대해서 깊이 생각해봤다.