[프로그래머스 Lv3] 정수 삼각형 - Javascript 풀이

문제

정수 삼각형이 주어졌을 때

꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾는 문제

 

생각

DP에 각 위치까지 도달했을 때의 최댓값을 저장하고,
마지막 줄(바닥)에 도달했을 때 그 중 가장 큰 값이 정답이라고 생각했다.

 

문제풀이

테이블을 정의해보자.

D[i][j] : 꼭대기에서 i번째 줄의 j번째 위치까지 도달했을 때 얻을 수 있는 최대 합
D[i] = f(D[i-1])

 

현재 값 triangle[i][j]을 K라고 하면, 점화식은 다음과 같다.

• j === 0 인 경우: 오른쪽 부모만 존재
• j === i 인 경우: 왼쪽 부모만 존재
• 그 외: 왼쪽/오른쪽 부모 모두 존재

D[i][j] = K + max(D[i-1][j], D[i-1][j-1])

 

시간복잡도는 O(N^2)이다.

 

이 외에도 더 효율적인 풀이들이 있다.
예를 들어 DP 배열을 따로 만들지 않고, triangle 배열을 직접 갱신하는 방법과

1차원 DP 배열만 사용하는 rolling array 방식 등이 존재한다.

 

두 방식 모두 점화식은 동일하지만,
구현 스타일에 따라 사용하는 메모리 양이 달라진다.

특히 triangle 배열을 직접 갱신하는 방법은
공간 복잡도를 O(N²)에서 O(1)로 줄일 수 있다는 장점이 있다.

 

 

코드

function solution(triangle) {
    const N = triangle.length
    const M = triangle[N-1].length
    const DP = Array.from({length: N}, () => Array(M).fill(0))
    
    DP[0][0] = triangle[0][0]
    
    for(let i=1; i<N; i++) {
        for(let j=0; j<triangle[i].length; j++) {
            const cost = triangle[i][j]
            
            if ( j===0 ) { // 오른쪽 부모만 존재
                DP[i][j] = DP[i-1][j] + cost
            } else if ( j===triangle[i].length-1 ) { // 왼쪽 부모만 존재
                DP[i][j] = DP[i-1][j-1] + cost
            } else { // 양쪽 부모 존재
                DP[i][j] = Math.max(DP[i-1][j] + cost, DP[i-1][j-1] + cost)
            }
        }
    }
    
    return Math.max(...DP[N-1])
}