programmers - 동적계획법 - 정수 삼각형

문제 설명

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

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

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

지난 연산의 값을 저장하고, 최대한 큰 값을 저장해야 되기 때문에 동적계획법 + 그리디 알고리즘의 성격을 띄고 있다.

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

역방향으로 가장 밑층부터 대소를 비교해서 누적 시켜주면 생각보다 쉽게 해결이 됨을 알 수 있다. 순차적으로 풀려고 하다가 이 풀이를 보고 가끔은 역발상이 엄청난 효율을 가져다 줄 수 있음을 참고했다.

참고 풀이 출처: https://allo-ew.tistory.com/120

아래는 직접 작성했던 코드

function solution(triangle) {
    let answer = 0;
    let x = [];
    let sum = [];
    let final = [];
    
    for( let i = 0; i < triangle.length-1 ; i++){
        for( let j = 0; j < i + 1; j++){
            if( i > 0){
                let a = sum[i-1][j-1];
                let b = sum[i-1][j];
                
                if( a !== undefined && b !== undefined){
                    sum[i][j] = sum[i-1][j-1] > sum[i-1][j] ?  sum[i-1][j-1] : sum[i-1][j];
                }
                else{
                    sum[i][j]= sum[i-1][j] + triangle[i][j];
                }
            }
            else{
                sum[i][j] = triangle[i][j]; 
            }
        }
    }
    
    answer = Math.max(...sum[triangle.length-1]);
    return answer;
}

+) python version

def solution(triangle):
    
    for i in range(len(triangle) - 2, -1, -1):
        for j in range(0, len(triangle[i])):
            triangle[i][j] += max(triangle[i + 1][j], triangle[i + 1][j + 1]) 
    
    return triangle[0][0]