[Programmers] 정수 삼각형

사용언어 : javascript

lv.3

문제풀이 소요시간 : 1시간 0분 41초

유형 : 동적 프로그래밍(DP)

 

#문제

출처 : 프로그래머스

#첫번째 제출코드

function solution(triangle) {
    var answer = 0;

    bfs(0, 0, triangle[0][0])
         
    function bfs(floor, pos, points){
        if(floor+1 === triangle.length ){
            if(answer < points){
                answer = points;
            }
            return;
        }
        
        if(floor < triangle.length){
            bfs(floor+1, pos, points + triangle[floor+1][pos]);
            bfs(floor+1, pos+1, points + triangle[floor+1][pos+1]);
        }
        
    }
    
    return answer;
}

(함수 이름이 잘못된 것 같지만 일단 넘어가자.)

 

처음에 문제를 이해했을땐, 어? 이거 노드를 하나씩 다 타고 내려가서 최대 값을 구하면 되는게 아닌가? 했다.

그래서 바로 재귀함수를 이용해서 풀었고, 시간이 생각보다 덜 소요돼서 뿌듯해했는데.. 이게 왠걸, time out으로 오답이 되었다.

 

답은 제대로 나오는데.. 뭐가 문제지?

 

한참을 문제를 곱씹다 보니, 재귀함수로 호출하기 때문에 삼각형의 높이가 500일 경우 소요시간이 아주 어마무시하게 늘어나는 거였다.

 

그럼 이걸 어떻게 시간을 줄일 수 있지? 최상위 꼭지점에서 내려가면서 해답을 찾으려면 어떻게 해도... 재귀 호출 밖에 생각이 안난다. 맨 위에서가 안되면.. 맨 아래서 가면 되지 않나..? 라는 생각이 들었다. 그리고 재귀 함수 호출이 시간을 잡아먹으면, 배열로 접근해보기로 했다.

 

맨 아래에서 양 옆의 배열 값을 비교해 큰 값을 가진 친구를 바로 윗층의 배열 값에 저장을 해주도록 하고, 최상단까지 올라가도록 코드를 작성해봤다. 

 

#최종 제출 코드

function solution(triangle) {
    const size = triangle.length-1;

    for(let i=size; i>0; i--){
        for(let j=0; j<triangle[i].length; j++){
            triangle[i-1][j] += triangle[i][j] > triangle[i][j+1] ? triangle[i][j] : triangle[i][j+1];
        }
    }
    return triangle[0][0];
}