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

📌 문제

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

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

 

💡 아이디어 

1. 처음 아이디어는 갈 수 있는 값들을 먼저 모아둔 다음에 제일 큰 값으로 가기 였는데 생각해보니, 방향성이 있기 때문에 더할 수 있는 값이 제한되어 있어서 계속 큰값을 더해준다고 해서 결과값이 최대가 되는 건 아니었다.

2. 각 요소에서 나올 수 있는 제일 큰 합을 가진 배열을 만들고, 그 배열에서 가장 큰 값을 뽑아내면 최대값을 찾을 수 있다.

sumList를 만드는 과정

완성된 sumList

 

✏️ 풀이

오답 풀이

function solution(triangle) {
    // 맨 처음 값 더하고, 
    // 0 -> 0, 1  1 -> 1, 2 자기자신, +1 된 인덱스로 갈 수 있음.
    // 다음 배열에서 제일 큰 값을 찾고 갈 수 있는 지 확인 -> 못 가면 그 다음 큰 값 찾기 X
    // 갈 수 있는 값들을 먼저 모아둔 다음에 제일 큰 값으로 가기
    let answer = 0;
    let current = 0;
    answer += triangle[0][0];
    for(let i=1; i<triangle.length; i++){
        let access = [triangle[i][current], triangle[i][current + 1]];
        let max = Math.max(...access);
        let maxIndex = triangle[i].indexOf(max);
        answer += max;
        current = maxIndex;   
    }
    return answer;
}

 

정답 풀이

function solution(triangle) {
    let answer = 0;
    let maxList = [[triangle[0][0]]];
    for(let i=1; i<triangle.length; i++){
        let sumList = [];
        for(let j=0; j<triangle[i].length; j++){
            if(j === 0) {
                sumList.push(triangle[i][j] + maxList[i-1][0]);
            }
            else if(j === triangle[i].length-1) {
                sumList.push(triangle[i][j] + maxList[i-1][j-1]);
            }
            else {
                if(maxList[i-1][j-1] > maxList[i-1][j]) {
                    sumList.push(triangle[i][j] + maxList[i-1][j-1]);
                }
                else {
                    sumList.push(triangle[i][j] + maxList[i-1][j]);
                }
            }
        }
        maxList.push(sumList);
    }
    return Math.max(...maxList[maxList.length-1]);
}