프로그래머스[JS] > 정수 삼각형

 

🔥문제링크

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

프로그래머스

 

 

🔥풀이

프로그래머스 홈페이지 코딩테스트 문제목록 위에 보면 AI 가 나를 분석해 추천해주는 문제가 있어서 그 문제를 풀어보았다. 알고리즘의 카테고리는 동적계획법으로 분류 되어 있었는데 정확히 동적계획법이 뭔지 궁금해서 찾아보니 ...

 이렇다고 한다. 계산화 최적화라고 생각하면 될 것같고 dynamic programming (DP) 이라고 한다

자 이제 진짜 풀이이다. 

function solution(triangle) {
    let sum_arr = []    
    triangle.forEach((arr)=>{
        if(sum_arr.length===0){
            sum_arr=arr
        }else{
            let temp = []
            for(let i=0; i<=arr.length-1; ++i){
                if(sum_arr[i-1]&&sum_arr[i]){
                    let max = Math.max(sum_arr[i-1],sum_arr[i])
                    temp.push(max+arr[i])
                }else if(i===arr.length-1){
                    temp.push(arr[i]+sum_arr[i-1])
                }else{
                    temp.push(arr[i]+sum_arr[i])   
                }
            }  
            sum_arr=temp
        }  
    })
    return Math.max(...sum_arr);
}

 

핵심은 지나온 수들의 합 중 최대를 구한다는 것과 if(sum_arr[i-1]&&sum_arr[i])  <- 이 조건을 인지하는 것이다.

예를들어 [ [1], [2,3] , [5,6,7] ] 이라는 삼각형이 주어 졌을때 6마지막 6으로 오는방법은 1->2->6 과 1->3->6 이 있다. 여기서 1->3->6 으로 오는 방법의 합이 더 크므로 1->2->6은 무시해도 되는 것이다. 이런식으로 삼각형의 각줄의 첫번째와 마지막 행을 제외하고는 최댓값만을 쌓아가며 마지막 삼각형 라인까지 오면 합산값들의 목록을 구할 수 있고 이 중 최대값을 return 하면 문제를 해결 할 수 있다.